結果

問題 No.1725 [Cherry 3rd Tune D] 無言の言葉
ユーザー warabi0906warabi0906
提出日時 2023-05-12 20:41:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 192 ms / 4,000 ms
コード長 3,483 bytes
コンパイル時間 1,681 ms
コンパイル使用メモリ 175,328 KB
実行使用メモリ 56,832 KB
最終ジャッジ日時 2024-05-06 10:26:17
合計ジャッジ時間 6,806 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 10 ms
5,376 KB
testcase_07 AC 5 ms
5,376 KB
testcase_08 AC 8 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 11 ms
6,364 KB
testcase_13 AC 12 ms
6,400 KB
testcase_14 AC 70 ms
6,272 KB
testcase_15 AC 14 ms
6,912 KB
testcase_16 AC 18 ms
7,424 KB
testcase_17 AC 32 ms
7,936 KB
testcase_18 AC 96 ms
5,888 KB
testcase_19 AC 28 ms
5,504 KB
testcase_20 AC 10 ms
5,376 KB
testcase_21 AC 73 ms
5,376 KB
testcase_22 AC 109 ms
20,480 KB
testcase_23 AC 99 ms
18,560 KB
testcase_24 AC 69 ms
13,952 KB
testcase_25 AC 123 ms
30,080 KB
testcase_26 AC 107 ms
24,064 KB
testcase_27 AC 119 ms
33,792 KB
testcase_28 AC 164 ms
32,256 KB
testcase_29 AC 149 ms
30,848 KB
testcase_30 AC 138 ms
36,736 KB
testcase_31 AC 73 ms
18,688 KB
testcase_32 AC 192 ms
49,152 KB
testcase_33 AC 192 ms
50,816 KB
testcase_34 AC 189 ms
47,104 KB
testcase_35 AC 164 ms
41,856 KB
testcase_36 AC 181 ms
46,336 KB
testcase_37 AC 107 ms
5,376 KB
testcase_38 AC 106 ms
5,376 KB
testcase_39 AC 105 ms
5,376 KB
testcase_40 AC 96 ms
5,376 KB
testcase_41 AC 99 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
testcase_43 AC 80 ms
56,832 KB
権限があれば一括ダウンロードができます

ソースコード

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){
            //cout<<ln<<endl;
            //cout<<l<<" "<<r<<endl;
            if(ln%2){
                if(rev(ln/2+1)==0)printf("%d\n",NxtY[l][C]+PrevY[r][C]-NxtY[0][C]);
                else printf("%d\n",NxtY[ys-r-1][C]+PrevY[ys-l-1][C]-NxtY[0][C]);
                
            }
            else{
                if((ln/2)%2)printf("%d\n",NxtX[xs-r-1][C]+PrevX[xs-l-1][C]-NxtX[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);
    }
    //cout<<xs<<" "<<ys<<endl;
    
    //for(int i=13;i<=43;i++)cout<<X[i];
    ////cout<<"\n";
    //for(int i=0;i<xs;i++){
    //    if(X[i]=='t')cout<<i<<" ";
    //}
    //cout<<"\n";
}
0