結果
問題 | No.1725 [Cherry 3rd Tune D] 無言の言葉 |
ユーザー |
|
提出日時 | 2023-05-12 20:16:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,955 bytes |
コンパイル時間 | 1,706 ms |
コンパイル使用メモリ | 175,924 KB |
実行使用メモリ | 56,704 KB |
最終ジャッジ日時 | 2024-11-28 16:14:27 |
合計ジャッジ時間 | 7,825 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 WA * 27 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int Limit=1e9+5; vector<int> Pow2; int L,R,C,res=0; #define debug cout<<"OK"<<__LINE__<<"\n"; int rev(int n){ //n回目に出現する文字列Yはreversedか? if(*lower_bound(Pow2.begin(),Pow2.end(),n)==n)return 0; auto itr=upper_bound(Pow2.begin(),Pow2.end(),n); assert(Pow2.begin()<itr); --itr; return rev(*itr*2-n)^1; } int even(int l,int r){ //[l,r]内の偶数 return r/2-(l-1)/2; } int odd(int l,int r){ //[l,r]内の奇数 return r-l+1-even(l,r); } int main(){ int p=1; while(p<Limit){ Pow2.push_back(p); p*=2; } //----- string X,Y; cin>>X>>Y; int xs=X.size(),ys=Y.size(); vector<vector<int>> NxtX(xs,vector<int>(26,0)),PrevX(xs,vector<int>(26,0));//Xのi文字目以降/以前にjはいくつ出現するか vector<vector<int>> NxtY(ys,vector<int>(26,0)),PrevY(ys,vector<int>(26,0));//Yのi文字目以降/以前にjはいくつ出現するか for(int i=0;i<xs;++i)for(int j=0;j<26;j++){ if(X[i]=='a'+j)PrevX[i][j]++; if(i<xs-1)PrevX[i+1][j]=PrevX[i][j]; } for(int i=xs-1;-1<i;--i)for(int j=0;j<26;j++){ if(X[i]=='a'+j)NxtX[i][j]++; if(0<i)NxtX[i-1][j]=NxtX[i][j]; } for(int i=0;i<ys;++i)for(int j=0;j<26;j++){ if(Y[i]=='a'+j)PrevY[i][j]++; if(i<ys-1)PrevY[i+1][j]=PrevY[i][j]; } for(int i=ys-1;-1<i;--i)for(int j=0;j<26;j++){ if(Y[i]=='a'+j)NxtY[i][j]++; if(0<i)NxtY[i-1][j]=NxtY[i][j]; } int Q;scanf("%d",&Q); while(Q--){ res=0; scanf("%d%d",&L,&R); char c; cin>>c; C=(int)(c-'a'); int ln=(L-1)/(xs+ys)*2+(int)(xs<=(L-1)%(xs+ys)),rn=(R-1)/(xs+ys)*2+(int)(xs<=(R-1)%(xs+ys));//L,R文字目は何個目の文字列? int l=(L-1)%(xs+ys);if(xs<=l)l-=xs; int r=(R-1)%(xs+ys);if(xs<=r)r-=xs; if(ln==rn){ if(ln%2)printf("%d\n",NxtY[l][C]+PrevY[r][C]-NxtY[0][C]); else printf("%d\n",NxtX[l][C]+PrevX[r][C]-NxtX[0][C]); continue; } if(ln+1<rn){ res+=odd(ln+1,rn-1)*NxtY[0][C]; res+=even(ln+1,rn-1)*NxtX[0][C]; //cout<<" "<<odd(ln+1,rn-1)<<" "<<NxtY[0][C]<<"\n"; //cout<<" "<<even(ln+1,rn-1)<<" "<<NxtX[0][C]<<"\n"; } //cout<<L<<" "<<R<<" "<<C<<endl; //cout<<l<<" "<<r<<endl; //cout<<ln<<" "<<rn<<endl; //cout<<res<<endl; if(ln%2){ if(rev(ln/2+1))res+=PrevY[ys-l-1][C]; else res+=NxtY[l][C]; } else{ if((ln/2)%2)res+=PrevX[xs-l-1][C]; else res+=NxtX[l][C]; } if(rn%2){ if(rev(rn/2+1))res+=NxtY[ys-r-1][C]; else res+=PrevY[r][C]; } else{ if((rn/2)%2)res+=NxtX[xs-r-1][C]; else res+=PrevX[r][C]; } printf("%d\n",res); } }