結果
問題 | No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに |
ユーザー | wanui |
提出日時 | 2022-10-15 01:51:02 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,104 ms / 6,000 ms |
コード長 | 4,251 bytes |
コンパイル時間 | 2,849 ms |
コンパイル使用メモリ | 229,104 KB |
実行使用メモリ | 48,112 KB |
最終ジャッジ日時 | 2024-06-26 19:07:42 |
合計ジャッジ時間 | 37,466 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 3 ms
5,376 KB |
testcase_02 | AC | 3 ms
5,376 KB |
testcase_03 | AC | 348 ms
23,644 KB |
testcase_04 | AC | 697 ms
29,424 KB |
testcase_05 | AC | 293 ms
23,600 KB |
testcase_06 | AC | 611 ms
26,804 KB |
testcase_07 | AC | 694 ms
27,424 KB |
testcase_08 | AC | 711 ms
29,484 KB |
testcase_09 | AC | 225 ms
15,812 KB |
testcase_10 | AC | 226 ms
14,740 KB |
testcase_11 | AC | 486 ms
25,988 KB |
testcase_12 | AC | 537 ms
26,068 KB |
testcase_13 | AC | 289 ms
15,652 KB |
testcase_14 | AC | 459 ms
19,392 KB |
testcase_15 | AC | 878 ms
30,244 KB |
testcase_16 | AC | 544 ms
26,324 KB |
testcase_17 | AC | 284 ms
16,008 KB |
testcase_18 | AC | 1,093 ms
47,832 KB |
testcase_19 | AC | 1,101 ms
47,980 KB |
testcase_20 | AC | 1,085 ms
47,980 KB |
testcase_21 | AC | 1,090 ms
47,852 KB |
testcase_22 | AC | 1,082 ms
47,980 KB |
testcase_23 | AC | 1,094 ms
47,856 KB |
testcase_24 | AC | 1,093 ms
47,856 KB |
testcase_25 | AC | 1,093 ms
47,984 KB |
testcase_26 | AC | 1,091 ms
47,852 KB |
testcase_27 | AC | 1,096 ms
48,112 KB |
testcase_28 | AC | 1,104 ms
47,984 KB |
testcase_29 | AC | 1,096 ms
47,988 KB |
testcase_30 | AC | 1,089 ms
48,112 KB |
testcase_31 | AC | 1,086 ms
47,984 KB |
testcase_32 | AC | 1,096 ms
47,988 KB |
testcase_33 | AC | 650 ms
47,980 KB |
testcase_34 | AC | 648 ms
47,984 KB |
testcase_35 | AC | 642 ms
48,040 KB |
testcase_36 | AC | 649 ms
47,984 KB |
testcase_37 | AC | 646 ms
47,988 KB |
testcase_38 | AC | 76 ms
20,260 KB |
testcase_39 | AC | 239 ms
20,292 KB |
testcase_40 | AC | 569 ms
47,988 KB |
testcase_41 | AC | 2 ms
5,376 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; }