結果
問題 | No.2338 Range AtCoder Query |
ユーザー | Rubikun |
提出日時 | 2023-06-02 22:28:03 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,397 ms / 4,000 ms |
コード長 | 3,514 bytes |
コンパイル時間 | 2,664 ms |
コンパイル使用メモリ | 220,408 KB |
実行使用メモリ | 278,540 KB |
最終ジャッジ日時 | 2023-08-28 04:24:06 |
合計ジャッジ時間 | 46,773 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 219 ms
272,256 KB |
testcase_01 | AC | 215 ms
272,140 KB |
testcase_02 | AC | 215 ms
272,260 KB |
testcase_03 | AC | 215 ms
272,136 KB |
testcase_04 | AC | 215 ms
272,176 KB |
testcase_05 | AC | 214 ms
272,132 KB |
testcase_06 | AC | 215 ms
272,180 KB |
testcase_07 | AC | 215 ms
272,176 KB |
testcase_08 | AC | 218 ms
272,436 KB |
testcase_09 | AC | 218 ms
272,216 KB |
testcase_10 | AC | 217 ms
272,168 KB |
testcase_11 | AC | 1,483 ms
276,468 KB |
testcase_12 | AC | 1,631 ms
276,480 KB |
testcase_13 | AC | 1,710 ms
276,536 KB |
testcase_14 | AC | 1,697 ms
276,044 KB |
testcase_15 | AC | 1,879 ms
277,460 KB |
testcase_16 | AC | 2,075 ms
278,336 KB |
testcase_17 | AC | 2,261 ms
278,332 KB |
testcase_18 | AC | 1,980 ms
278,404 KB |
testcase_19 | AC | 2,079 ms
278,324 KB |
testcase_20 | AC | 2,047 ms
278,408 KB |
testcase_21 | AC | 2,397 ms
278,340 KB |
testcase_22 | AC | 2,074 ms
278,384 KB |
testcase_23 | AC | 2,163 ms
278,540 KB |
testcase_24 | AC | 2,012 ms
278,332 KB |
testcase_25 | AC | 2,110 ms
278,384 KB |
testcase_26 | AC | 271 ms
273,496 KB |
testcase_27 | AC | 252 ms
273,648 KB |
testcase_28 | AC | 256 ms
273,552 KB |
testcase_29 | AC | 1,697 ms
278,332 KB |
testcase_30 | AC | 2,215 ms
278,332 KB |
testcase_31 | AC | 1,238 ms
278,500 KB |
testcase_32 | AC | 1,154 ms
278,320 KB |
testcase_33 | AC | 395 ms
278,404 KB |
testcase_34 | AC | 392 ms
278,404 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } #define all(x) (x).begin(),(x).end() #define fi first #define se second #define mp make_pair #define si(x) int(x.size()) const int mod=998244353,MAX=200005,INF=1<<30; struct dat{ int l; int r; int id; }; deque<int> AC[MAX],WA[MAX]; const int D=800; int main(){ std::ifstream in("text.txt"); std::cin.rdbuf(in.rdbuf()); cin.tie(0); ios::sync_with_stdio(false); int N,M,Q;cin>>N>>M>>Q; vector<int> A(N); for(int i=0;i<N;i++){ int x;cin>>x;x--; string S;cin>>S; if(S=="AC") A[i]=x; else A[i]=~x; } int l=-1,r=-1; vector<dat> S(Q); vector<pair<int,int>> ans(Q); for(int i=0;i<Q;i++){ cin>>S[i].l>>S[i].r; S[i].l--; S[i].r--; S[i].id=i; } vector<int> usel; for(int i=0;i<Q;i++) usel.push_back(S[i].l/D); sort(all(usel)); usel.erase(unique(all(usel)),usel.end()); vector<int> ty(N); for(int i=0;i<si(usel);i++){ ty[usel[i]]=i&1; } sort(all(S),[&](auto a,auto b){ if(a.l/D==b.l/D){ if(ty[a.l/D]) return a.r>b.r; else return a.r<b.r; } return a.l/D<b.l/D; }); int ac=0,wa=0; for(int i=0;i<Q;i++){ while(S[i].r>r){ r++; if(A[r]>=0){ int x=A[r]; if(si(AC[x])==0){ wa+=si(WA[x]); ac++; } AC[x].push_back(r); }else{ int x=~A[r]; WA[x].push_back(r); } } while(S[i].l<l){ l--; if(A[l]>=0){ int x=A[l]; if(si(AC[x])>=1){ int ne=AC[x][0]; wa-=lower_bound(all(WA[x]),ne)-WA[x].begin(); }else{ ac++; } AC[x].push_front(l); }else{ int x=~A[l]; if(si(AC[x])>=1){ wa++; } WA[x].push_front(l); } } while(S[i].r<r){ if(A[r]>=0){ int x=A[r]; if(si(AC[x])==1){ wa-=si(WA[x]); ac--; } AC[x].pop_back(); }else{ int x=~A[r]; WA[x].pop_back(); } r--; } while(S[i].l>l){ if(l>=0){ if(A[l]>=0){ int x=A[l]; if(si(AC[x])==1){ ac--; }else{ int ne=AC[x][1]; wa+=lower_bound(all(WA[x]),ne)-WA[x].begin(); } AC[x].pop_front(); }else{ int x=~A[l]; if(si(AC[x])>=1){ wa--; } WA[x].pop_front(); } } l++; } ans[S[i].id]=mp(ac,wa); //break; } for(int i=0;i<Q;i++) cout<<ans[i].fi<<" "<<ans[i].se<<"\n"; }