結果

問題 No.1725 [Cherry 3rd Tune D] 無言の言葉
コンテスト
ユーザー warabi0906
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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);
    }
}
0