結果
問題 | No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに |
ユーザー | wanui |
提出日時 | 2022-10-15 02:22:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,276 ms / 6,000 ms |
コード長 | 2,838 bytes |
コンパイル時間 | 3,727 ms |
コンパイル使用メモリ | 217,772 KB |
実行使用メモリ | 20,540 KB |
最終ジャッジ日時 | 2023-09-09 01:58:13 |
合計ジャッジ時間 | 42,382 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,384 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,384 KB |
testcase_03 | AC | 354 ms
11,524 KB |
testcase_04 | AC | 821 ms
13,244 KB |
testcase_05 | AC | 361 ms
11,240 KB |
testcase_06 | AC | 716 ms
13,604 KB |
testcase_07 | AC | 809 ms
13,916 KB |
testcase_08 | AC | 829 ms
13,788 KB |
testcase_09 | AC | 285 ms
8,416 KB |
testcase_10 | AC | 296 ms
7,952 KB |
testcase_11 | AC | 585 ms
12,408 KB |
testcase_12 | AC | 594 ms
12,544 KB |
testcase_13 | AC | 359 ms
8,584 KB |
testcase_14 | AC | 503 ms
10,336 KB |
testcase_15 | AC | 978 ms
15,088 KB |
testcase_16 | AC | 622 ms
13,300 KB |
testcase_17 | AC | 335 ms
7,736 KB |
testcase_18 | AC | 1,259 ms
20,236 KB |
testcase_19 | AC | 1,256 ms
20,148 KB |
testcase_20 | AC | 1,261 ms
20,320 KB |
testcase_21 | AC | 1,259 ms
19,612 KB |
testcase_22 | AC | 1,276 ms
19,816 KB |
testcase_23 | AC | 1,264 ms
20,216 KB |
testcase_24 | AC | 1,263 ms
19,616 KB |
testcase_25 | AC | 1,254 ms
20,384 KB |
testcase_26 | AC | 1,264 ms
20,180 KB |
testcase_27 | AC | 1,261 ms
20,068 KB |
testcase_28 | AC | 1,266 ms
19,996 KB |
testcase_29 | AC | 1,275 ms
19,684 KB |
testcase_30 | AC | 1,270 ms
19,712 KB |
testcase_31 | AC | 1,259 ms
20,348 KB |
testcase_32 | AC | 1,257 ms
20,540 KB |
testcase_33 | AC | 825 ms
19,904 KB |
testcase_34 | AC | 824 ms
19,708 KB |
testcase_35 | AC | 823 ms
20,540 KB |
testcase_36 | AC | 822 ms
19,560 KB |
testcase_37 | AC | 823 ms
19,436 KB |
testcase_38 | AC | 140 ms
10,752 KB |
testcase_39 | AC | 345 ms
10,664 KB |
testcase_40 | AC | 765 ms
20,060 KB |
testcase_41 | AC | 2 ms
4,384 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const int SQ = 500; using tii = tuple<int, int, int>; int main() { // 場所ごとに「減り始めるイベント」「減らなくなるイベント」が1回ずつある // 地獄のような平方分割 int N; cin >> N; vector<int> A(N); vector<int> T(N); for (int i = 0; i < N; i++) { cin >> A[i] >> T[i]; } int Q; cin >> Q; vector<tii> queries; for (int i = 0; i < Q; i++) { int d, l, r; cin >> d >> l >> r; l--; r--; queries.push_back({d, l, r}); } vector<tii> evt; for (int i = 0; i < N; i++) { int t = T[i]; evt.push_back({t, -1, i}); int t2 = A[i] + T[i] - 1; evt.push_back({t2, 1, i}); } for (int i = 0; i < Q; i++) { int d, l, r; tie(d, l, r) = queries[i]; evt.push_back({d, 9, i}); } vector<int> i2b(N); for (int i = 0; i < N; i++) { i2b[i] = (i / SQ); } int BK = i2b[N - 1] + 1; vector<vector<int>> b2i(BK); for (int i = 0; i < N; i++) { int b = i2b[i]; b2i[b].push_back(i); } vector<int> bleft(BK); vector<int> bright(BK); vector<ll> sum(BK); vector<int> diff(BK, 0); for (int b = 0; b < BK; b++) { ll s = 0; for (auto i : b2i[b]) { s += A[i]; } sum[b] = s; bleft[b] = b2i[b][0]; bright[b] = b2i[b].back(); } vector<ll> ans(Q); int pre_time = 0; sort(evt.begin(), evt.end()); for (auto e : evt) { int time, kind, ind; tie(time, kind, ind) = e; for (int b = 0; b < BK; b++) { sum[b] += 1ll * diff[b] * (time - pre_time); } if (kind == 9) { int _d, l, r; tie(_d, l, r) = queries[ind]; ll s = 0; for (int b = 0; b < BK; b++) { if (l <= bleft[b] && bright[b] <= r) { s += sum[b]; continue; } if (r < bleft[b]) continue; if (bright[b] < l) continue; for (auto i : b2i[b]) { if (l <= i && i <= r) { ll now = A[i]; if (time >= T[i]) { now -= time - T[i] + 1; if (now < 0) now = 0; } s += now; } } } ans[ind] = s; } else { int d = kind; int b = i2b[ind]; if (d < 0) sum[b]--; diff[b] += d; } pre_time = time; } for (int q = 0; q < Q; q++) { cout << ans[q] << "\n"; } return 0; }