結果
問題 | No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに |
ユーザー | wanui |
提出日時 | 2022-10-15 01:51:02 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,303 ms / 6,000 ms |
コード長 | 4,251 bytes |
コンパイル時間 | 4,168 ms |
コンパイル使用メモリ | 224,564 KB |
実行使用メモリ | 49,700 KB |
最終ジャッジ日時 | 2023-09-09 01:50:17 |
合計ジャッジ時間 | 40,097 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 320 ms
24,212 KB |
testcase_04 | AC | 840 ms
29,424 KB |
testcase_05 | AC | 355 ms
23,940 KB |
testcase_06 | AC | 738 ms
26,596 KB |
testcase_07 | AC | 793 ms
27,248 KB |
testcase_08 | AC | 861 ms
30,440 KB |
testcase_09 | AC | 259 ms
15,508 KB |
testcase_10 | AC | 271 ms
15,568 KB |
testcase_11 | AC | 591 ms
27,292 KB |
testcase_12 | AC | 597 ms
26,152 KB |
testcase_13 | AC | 340 ms
15,488 KB |
testcase_14 | AC | 546 ms
19,988 KB |
testcase_15 | AC | 974 ms
30,128 KB |
testcase_16 | AC | 582 ms
26,316 KB |
testcase_17 | AC | 355 ms
17,420 KB |
testcase_18 | AC | 1,270 ms
48,268 KB |
testcase_19 | AC | 1,297 ms
48,008 KB |
testcase_20 | AC | 1,268 ms
47,912 KB |
testcase_21 | AC | 1,262 ms
47,744 KB |
testcase_22 | AC | 1,303 ms
47,968 KB |
testcase_23 | AC | 1,265 ms
48,160 KB |
testcase_24 | AC | 1,254 ms
49,352 KB |
testcase_25 | AC | 1,276 ms
48,136 KB |
testcase_26 | AC | 1,287 ms
48,912 KB |
testcase_27 | AC | 1,293 ms
48,124 KB |
testcase_28 | AC | 1,249 ms
48,384 KB |
testcase_29 | AC | 1,078 ms
48,012 KB |
testcase_30 | AC | 1,067 ms
48,164 KB |
testcase_31 | AC | 1,066 ms
49,700 KB |
testcase_32 | AC | 1,060 ms
48,028 KB |
testcase_33 | AC | 519 ms
47,988 KB |
testcase_34 | AC | 513 ms
47,968 KB |
testcase_35 | AC | 513 ms
47,580 KB |
testcase_36 | AC | 517 ms
48,116 KB |
testcase_37 | AC | 519 ms
48,148 KB |
testcase_38 | AC | 66 ms
20,580 KB |
testcase_39 | AC | 250 ms
20,592 KB |
testcase_40 | AC | 470 ms
48,496 KB |
testcase_41 | AC | 1 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18; void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);} void print(){print0("\n");}; template<typename H,typename... T>void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);} void perr0(){}; template<typename H,typename... T> void perr0(H h,T... t){cerr<<h;perr0(t...);} void perr(){perr0("\n");}; template<typename H,typename... T>void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);} void ioinit() { cout<<fixed<<setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); } #define debug1(a) { cerr<<#a<<":"<<a<<endl; } #define debug2(a,b) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; } #define debug3(a,b,c) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; } #define debug4(a,b,c,d) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; } // clang-format on int main() { // 場所ごとに「減り始めるイベント」「減らなくなるイベント」が1回ずつある // 地獄のような平方分割 ioinit(); ll N; cin >> N; vector<pll> AT(N); for (ll i = 0; i < N; i++) { cin >> AT[i].first >> AT[i].second; } ll Q; cin >> Q; using tll = tuple<ll, ll, ll>; using qll = tuple<ll, ll, ll, ll>; vector<tll> queries; for (ll i = 0; i < Q; i++) { ll d, l, r; cin >> d >> l >> r; l--; r--; queries.push_back({d, l, r}); } vector<qll> evt; for (ll i = 0; i < N; i++) { ll t = AT[i].second; evt.push_back({t, 0, -1, i}); ll t2 = AT[i].first + AT[i].second - 1; evt.push_back({t2, 0, 1, i}); } for (ll i = 0; i < Q; i++) { ll d, l, r; tie(d, l, r) = queries[i]; evt.push_back({d, 1, i, i}); } const ll SQ = 500; vector<ll> i2b(N); for (ll i = 0; i < N; i++) { i2b[i] = (i / SQ); } ll BK = i2b[N - 1] + 1; vector<vector<ll>> b2i(BK); vector<ll> bleft(BK, INF); vector<ll> bright(BK, -1); for (ll i = 0; i < N; i++) { ll b = i2b[i]; b2i[b].push_back(i); bleft[b] = min(bleft[b], i); bright[b] = max(bright[b], i); } vector<ll> sum(BK); vector<ll> diff(BK, 0); for (ll b = 0; b < BK; b++) { ll s = 0; for (auto i : b2i[b]) { s += AT[i].first; } sum[b] = s; } vector<ll> ans(Q); ll pre_tim = 0; sort(evt.begin(), evt.end()); for (auto e : evt) { ll tim, kind, _tmp, _tmp2; tie(tim, kind, _tmp, _tmp2) = e; ll tim_diff = tim - pre_tim; if (kind == 1) { ll qid = _tmp; for (ll b = 0; b < BK; b++) { sum[b] += diff[b] * tim_diff; } ll d, l, r; tie(d, l, r) = queries[qid]; ll s = 0; { for (ll 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 = AT[i].first; if (tim >= AT[i].second) { now -= tim - AT[i].second + 1; if (now < 0) now = 0; } s += now; } } } } ans[qid] = s; } else { ll d = _tmp; ll i = _tmp2; for (ll b = 0; b < BK; b++) { sum[b] += diff[b] * tim_diff; } if (d < 0) sum[i2b[i]]--; diff[i2b[i]] += d; // debug3(tim, diff[0], sum[0]); } pre_tim = tim; } for (ll q = 0; q < Q; q++) { print(ans[q]); } return 0; }