結果
問題 | No.2338 Range AtCoder Query |
ユーザー |
|
提出日時 | 2023-06-02 22:14:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,960 bytes |
コンパイル時間 | 1,310 ms |
コンパイル使用メモリ | 90,636 KB |
実行使用メモリ | 285,868 KB |
最終ジャッジ日時 | 2024-12-28 18:48:01 |
合計ジャッジ時間 | 77,270 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 23 TLE * 11 |
ソースコード
#include<iostream>#include<map>#include<vector>#include<algorithm>#include<deque>#include<cassert>using namespace std;int ALL,CNT;struct deq{deque<int>WA;deq(){WA.push_back(0);}void push_front(bool s){if(s){if(WA.size()>=2)ALL-=WA.front();else CNT++;WA.push_front(0);}else{if(WA.size()>=2)ALL++;WA.front()++;}}void push_back(bool s){if(s){if(WA.size()==1)CNT++,ALL+=WA.front();WA.push_back(0);}else WA.back()++;}void pop_front(){if(WA.front()>0){if(WA.size()>=2)ALL--;WA.front()--;}else{WA.pop_front();if(WA.size()>=2)ALL+=WA.front();else CNT--;}}void pop_back(){if(WA.back()>0)WA.back()--;else{WA.pop_back();if(WA.size()==1){CNT--;ALL-=WA.front();}}}};int N,M,Q;int P[2<<17];bool S[2<<17];deq A[200000];const int B=1000;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";}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++){sort(qR[li].begin(),qR[li].end(),[&li](const pair<int,pair<int,int> >&l,const pair<int,pair<int,int> >&r){if(li&1)return l.first>r.first;else 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){nL--;A[P[nL]].push_front(S[nL]);}while(nR<r){A[P[nR]].push_back(S[nR]);nR++;}while(nL<l){A[P[nL]].pop_front();nL++;}while(nR>r){nR--;A[P[nR]].pop_back();}cnt[p.second.second]=CNT;ans[p.second.second]=ALL;}}for(int i=0;i<Q;i++)cout<<cnt[i]<<" "<<ans[i]<<"\n";}