想定ではなかったのね…。
https://yukicoder.me/problems/no/2338
問題
M問の問題があり、N回分の提出情報がある。
各提出情報は、提出した問題の番号と、結果(AC/WA)が与えられる。
提出情報の区間を示すクエリに対し、以下を答えよ。
- 区間内の順に提出した場合、ユニークな問題に対するAC数と、それらの初回AC前のWA回数の総和を求めよ。
解法
Mo's Algorithmで解ける。
ACで区切られたWAの回数をdequeで管理し、AC/WAの数をカウントしよう。
ただdequeは処理が重くTLEするので、以下では長い配列を区切ってdeque的な使い方をしている。
int N,M,Q; int P[202020],S[202020]; int L[202020],R[202020],ac[202020],wa[202020]; int PL[202020],PR[202020]; int num[202020]; int start[202020]; int AC[808080]; vector<pair<int,int>> ev[202020]; const int DI=800; int nac=0,nwa=0; void add1(int pos) { int p=P[pos]; if(S[pos]==0) { AC[PR[p]]++; } else { if(PL[p]==PR[p]) { nac++; nwa+=AC[PL[p]]; } PR[p]++; } } void add2(int pos) { int p=P[pos]; if(S[pos]==0) { AC[PL[p]]++; if(PL[p]<PR[p]) nwa++; } else { if(PL[p]==PR[p]) { nac++; } else { nwa-=AC[PL[p]]; } PL[p]--; } } void del(int pos) { int p=P[pos]; if(S[pos]==0) { AC[PL[p]]--; if(PL[p]<PR[p]) nwa--; } else { PL[p]++; if(PL[p]==PR[p]) { nac--; } else { nwa+=AC[PL[p]]; } } } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>Q; FOR(i,N) { cin>>P[i]>>s; S[i]=s=="AC"; num[P[i]]++; } FOR(i,Q) { cin>>L[i]>>R[i]; L[i]--; ev[L[i]/DI].push_back({R[i],i}); } int sum=0; FOR(i,M+1) { PL[i]=PR[i]=start[i]=sum+num[i]; sum+=num[i]*2; } FOR(i,201000) if(ev[i].size()) { sort(ALL(ev[i])); int CL=i*DI,CR=i*DI; FORR2(r,cur,ev[i]) { int TL=L[cur],TR=r; while(CR<TR) add1(CR++); while(TL<CL) add2(--CL); while(CL<TL) del(CL++); ac[cur]=nac; wa[cur]=nwa; } while(CL<CR) del(CL++); FOR(j,M+1) PL[j]=PR[j]=start[j]; } FOR(i,Q) { cout<<ac[i]<<" "<<wa[i]<<endl; } }
まとめ
dequeで組んだ後TLEへの対処に苦労したが、想定解ではなかったのね…。