結果
問題 |
No.2698 Many Asakatsu
|
ユーザー |
![]() |
提出日時 | 2024-03-23 08:58:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,760 bytes |
コンパイル時間 | 1,771 ms |
コンパイル使用メモリ | 201,172 KB |
最終ジャッジ日時 | 2025-02-20 13:06:48 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 4 WA * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long INF = 1000000000000000000; int main(){ int N, M; cin >> N >> M; vector<long long> A(N), B(N); for (int i = 0; i < N; i++){ cin >> A[i] >> B[i]; } int Q, X; cin >> Q >> X; vector<int> C(N); for (int i = 0; i < N; i++){ cin >> C[i]; } int p = 0; auto d = [&](int i, long long R){ if (R <= A[i]){ return (A[i] - R) * M + B[i] * M * (M - 1) / 2; } else if (A[i] + B[i] * (M - 1) <= R){ return R * M - (A[i] * 2 + B[i] * (M - 1)) * M / 2; } else { int p = (R - A[i]) / B[i]; long long ans = 0; ans += (R * 2 - A[i] * 2 - B[i] * p) * (p + 1) / 2; ans += (A[i] * 2 + B[i] * (M + p) - R * 2) * (M - p - 1) / 2; return ans; } }; struct node{ int l, r; int idx; node* lch; node* rch; node(int l, int r, int idx): l(l), r(r), idx(idx), lch(nullptr), rch(nullptr){ } }; node* root = new node(0, 1000000000, 0); auto line_add = [&](auto line_add, int idx, node* v){ long long la = d(v->idx, v->l); long long lb = d(idx, v->l); long long ra = d(v->idx, v->r); long long rb = d(idx, v->r); if (make_pair(la, v->idx) >= make_pair(lb, idx) && make_pair(ra, v->idx) >= make_pair(rb, idx)){ return; } else if (make_pair(la, v->idx) <= make_pair(lb, idx) && make_pair(ra, v->idx) <= make_pair(rb, idx)){ v->idx = idx; } else { int m = (v->l + v->r) / 2; long long ma = d(v->idx, m); long long mb = d(idx, m); if (make_pair(ma, v->idx) < make_pair(mb, idx)){ swap(v->idx, idx); swap(la, lb); swap(ra, rb); } if (make_pair(la, v->idx) < make_pair(lb, idx)){ if (v->lch == nullptr){ v->lch = new node(v->l, m, idx); } else { line_add(line_add, idx, v->lch); } } if (make_pair(ra, v->idx) < make_pair(rb, idx)){ if (v->rch == nullptr){ v->rch = new node(m + 1, v->r, idx); } else { line_add(line_add, idx, v->rch); } } } }; auto get_min = [&](int x){ int idx = -1; node* v = root; while (true){ if (v == nullptr){ break; } if (idx == -1){ idx = v->idx; } else if (make_pair(d(v->idx, x), v->idx) < make_pair(d(idx, x), idx)){ idx = v->idx; } if (x <= (v->l + v->r) / 2){ v = v->lch; } else { v = v->rch; } } return idx; }; for (int i = 1; i < N; i++){ line_add(line_add, i, root); } for (int i = 0; i < Q; i++){ X = min(X, 1000000000); int p = get_min(X); cout << p + 1; X += C[p]; if (i < Q - 1){ cout << ' '; } } cout << endl; }