結果
問題 | No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに |
ユーザー | momoyuu |
提出日時 | 2022-10-15 00:28:55 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 527 ms / 6,000 ms |
コード長 | 2,487 bytes |
コンパイル時間 | 4,442 ms |
コンパイル使用メモリ | 256,452 KB |
実行使用メモリ | 32,248 KB |
最終ジャッジ日時 | 2023-09-09 01:17:21 |
合計ジャッジ時間 | 26,243 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 219 ms
16,624 KB |
testcase_04 | AC | 370 ms
19,540 KB |
testcase_05 | AC | 207 ms
16,564 KB |
testcase_06 | AC | 331 ms
18,280 KB |
testcase_07 | AC | 376 ms
19,636 KB |
testcase_08 | AC | 365 ms
18,788 KB |
testcase_09 | AC | 174 ms
11,512 KB |
testcase_10 | AC | 164 ms
10,876 KB |
testcase_11 | AC | 269 ms
18,040 KB |
testcase_12 | AC | 271 ms
18,196 KB |
testcase_13 | AC | 185 ms
11,648 KB |
testcase_14 | AC | 204 ms
11,640 KB |
testcase_15 | AC | 428 ms
21,512 KB |
testcase_16 | AC | 325 ms
18,184 KB |
testcase_17 | AC | 146 ms
11,092 KB |
testcase_18 | AC | 523 ms
30,656 KB |
testcase_19 | AC | 524 ms
30,720 KB |
testcase_20 | AC | 527 ms
31,048 KB |
testcase_21 | AC | 513 ms
31,944 KB |
testcase_22 | AC | 521 ms
31,600 KB |
testcase_23 | AC | 518 ms
30,712 KB |
testcase_24 | AC | 525 ms
31,120 KB |
testcase_25 | AC | 526 ms
31,116 KB |
testcase_26 | AC | 515 ms
31,864 KB |
testcase_27 | AC | 520 ms
31,664 KB |
testcase_28 | AC | 524 ms
30,604 KB |
testcase_29 | AC | 523 ms
31,316 KB |
testcase_30 | AC | 522 ms
32,248 KB |
testcase_31 | AC | 524 ms
30,816 KB |
testcase_32 | AC | 524 ms
31,804 KB |
testcase_33 | AC | 473 ms
30,988 KB |
testcase_34 | AC | 475 ms
31,104 KB |
testcase_35 | AC | 477 ms
30,736 KB |
testcase_36 | AC | 472 ms
31,584 KB |
testcase_37 | AC | 479 ms
30,452 KB |
testcase_38 | AC | 140 ms
12,512 KB |
testcase_39 | AC | 246 ms
13,628 KB |
testcase_40 | AC | 426 ms
31,232 KB |
testcase_41 | AC | 1 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; template<class t> using vc = vector<t>; template<class t> using vvc = vc<vc<t>>; using pi = pair<int,int>; using pl = pair<ll,ll>; using vi = vc<int>; using vvi = vvc<int>; using vl = vc<ll>; using vvl = vvc<ll>; #define rep(i,a,b) for (int i = (int)(a); i < (int)(b); i++) #define irep(i,a,b) for (int i = (int)(a); i > (int)(b); i--) #define all(a) a.begin(),a.end() #define print(n) cout << n << '\n' #define pritn(n) print(n) #define printv(n,a) {copy(all(n),ostream_iterator<a>(cout," ")); cout<<"\n";} #define printvv(n,a) {for(auto itr:n) printv(itr,a);} #define rup(a,b) (a+b-1)/b #define input(A,N) rep(i,0,N) cin>>A[i] #define chmax(a,b) a = max(a,b) #define chmin(a,b) a = min(a,b) template< typename T > struct BIT{ int n; vector<T> data; BIT(int n):n(n),data(n+1,0){} void add(int i,T x){ i++; while(i<=n){ data[i] += x; i += i & (-i); } } //sum of [l,r) T sum(int l,int r){ return sum(r-1)-sum(l-1); } T sum(int i){ i++; T now = 0; while(i>0){ now += data[i]; i -= i & (-i); } return now; } }; int main(){ cout << fixed << setprecision(15); int n; cin>>n; BIT<ll> b1(n),b2(n); using pp = pair<ll,pair<int,int>>; vc<pp> dd; vl a(n); vl t(n); rep(i,0,n){ cin>>a[i]>>t[i]; b1.add(i,a[i]); dd.emplace_back(t[i]-1,pi(0,i)); dd.emplace_back(t[i]+a[i]-1,pi(1,i)); } int q; cin>>q; vl tt(q),l(q),r(q); rep(i,0,q){ cin>>tt[i]>>l[i]>>r[i]; l[i]--; dd.emplace_back(tt[i],pi(2,i)); } sort(all(dd)); vl ans(q); //a[i] - (nt - t[i] + 1) rep(i,0,dd.size()){ pp now = dd[i]; int qq = now.second.first; ll nn = now.first; int ni = now.second.second; //cout<<ni<<" "<<nn<<" "<<qq<<endl; if(qq==0){ b1.add(ni,nn); b2.add(ni,-1); }else if(qq==1){ b1.add(ni,-(nn-a[ni])); b1.add(ni,-a[ni]); b2.add(ni,1); }else{ //cout<<l[ni]<<" "<<r[ni]<<endl; ll sum = b1.sum(l[ni],r[ni]) + nn*b2.sum(l[ni],r[ni]); ans[ni] = sum; } } rep(i,0,q) print(ans[i]); //system("pause"); return 0; }