結果
問題 | No.2338 Range AtCoder Query |
ユーザー | kotatsugame |
提出日時 | 2023-06-02 22:28:46 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,642 ms / 4,000 ms |
コード長 | 2,067 bytes |
コンパイル時間 | 1,272 ms |
コンパイル使用メモリ | 90,672 KB |
実行使用メモリ | 37,088 KB |
最終ジャッジ日時 | 2023-08-28 04:25:48 |
合計ジャッジ時間 | 39,851 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
19,812 KB |
testcase_01 | AC | 6 ms
19,816 KB |
testcase_02 | AC | 7 ms
19,820 KB |
testcase_03 | AC | 6 ms
19,764 KB |
testcase_04 | AC | 6 ms
20,080 KB |
testcase_05 | AC | 6 ms
19,828 KB |
testcase_06 | AC | 9 ms
19,952 KB |
testcase_07 | AC | 8 ms
19,828 KB |
testcase_08 | AC | 9 ms
20,036 KB |
testcase_09 | AC | 9 ms
20,156 KB |
testcase_10 | AC | 9 ms
19,880 KB |
testcase_11 | AC | 1,392 ms
28,740 KB |
testcase_12 | AC | 1,282 ms
28,808 KB |
testcase_13 | AC | 1,478 ms
28,948 KB |
testcase_14 | AC | 1,425 ms
28,100 KB |
testcase_15 | AC | 1,642 ms
29,672 KB |
testcase_16 | AC | 2,066 ms
32,396 KB |
testcase_17 | AC | 2,111 ms
32,572 KB |
testcase_18 | AC | 1,999 ms
32,592 KB |
testcase_19 | AC | 1,953 ms
32,628 KB |
testcase_20 | AC | 1,945 ms
32,588 KB |
testcase_21 | AC | 2,013 ms
32,656 KB |
testcase_22 | AC | 2,222 ms
32,312 KB |
testcase_23 | AC | 2,333 ms
32,596 KB |
testcase_24 | AC | 2,156 ms
32,660 KB |
testcase_25 | AC | 2,145 ms
32,592 KB |
testcase_26 | AC | 113 ms
27,704 KB |
testcase_27 | AC | 100 ms
27,796 KB |
testcase_28 | AC | 105 ms
27,716 KB |
testcase_29 | AC | 882 ms
32,312 KB |
testcase_30 | AC | 2,642 ms
32,652 KB |
testcase_31 | AC | 1,154 ms
37,088 KB |
testcase_32 | AC | 743 ms
37,064 KB |
testcase_33 | AC | 271 ms
31,552 KB |
testcase_34 | AC | 260 ms
31,508 KB |
ソースコード
#include<iostream> #include<map> #include<vector> #include<algorithm> #include<deque> #include<cassert> using namespace std; int ALL,CNT; int P[2<<17]; bool S[2<<17]; vector<int>idx[2<<17]; vector<int>nxt[2<<17]; int ac[2<<17]; int L[2<<17],R[2<<17]; void inc(int); void dec(int); void push_front(int id) { dec(P[id]); L[P[id]]--; if(S[id])ac[P[id]]++; inc(P[id]); } void push_back(int id) { dec(P[id]); R[P[id]]++; if(S[id])ac[P[id]]++; inc(P[id]); } void pop_front(int id) { dec(P[id]); L[P[id]]++; if(S[id])ac[P[id]]--; inc(P[id]); } void pop_back(int id) { dec(P[id]); R[P[id]]--; if(S[id])ac[P[id]]--; inc(P[id]); } void dec(int p) { if(ac[p]>=1) { ALL-=nxt[p][L[p]]; CNT--; } } void inc(int p) { if(ac[p]>=1) { ALL+=nxt[p][L[p]]; CNT++; } } int N,M,Q; const int B=500; const int MN=200000; vector<pair<int,pair<int,int> > >qR[(MN+B-1)/B]; int cnt[2<<17],ans[2<<17]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N>>M>>Q; for(int i=0;i<N;i++) { string s; cin>>P[i]>>s; P[i]--; S[i]=s=="AC"; idx[P[i]].push_back(i); } for(int i=0;i<M;i++) { nxt[i].resize(idx[i].size()); int c=0; for(int j=nxt[i].size();j--;) { if(S[idx[i][j]])c=0; else c++; nxt[i][j]=c; } } for(int i=0;i<Q;i++) { int l,r;cin>>l>>r; l--; qR[l/B].push_back(make_pair(r,make_pair(l,i))); } int nL=0,nR=0; for(int li=0;li*B<N;li++) { if(li&1) { sort(qR[li].begin(),qR[li].end(),[&li](const pair<int,pair<int,int> >&l,const pair<int,pair<int,int> >&r) { return l.first>r.first; }); } else { sort(qR[li].begin(),qR[li].end(),[&li](const pair<int,pair<int,int> >&l,const pair<int,pair<int,int> >&r) { return l.first<r.first; }); } for(pair<int,pair<int,int> >p:qR[li]) { int l=p.second.first; int r=p.first; while(nL>l)push_front(--nL); while(nR<r)push_back(nR++); while(nL<l)pop_front(nL++); while(nR>r)pop_back(--nR); cnt[p.second.second]=CNT; ans[p.second.second]=ALL; } } for(int i=0;i<Q;i++)cout<<cnt[i]<<" "<<ans[i]<<"\n"; }