結果

問題 No.2338 Range AtCoder Query
ユーザー kotatsugame
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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";
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0