結果

問題 No.1725 [Cherry 3rd Tune D] 無言の言葉
ユーザー warabi0906warabi0906
提出日時 2023-05-12 20:41:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 190 ms / 4,000 ms
コード長 3,483 bytes
コンパイル時間 1,648 ms
コンパイル使用メモリ 173,208 KB
実行使用メモリ 56,352 KB
最終ジャッジ日時 2023-08-19 03:18:43
合計ジャッジ時間 7,163 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge9
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,388 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 4 ms
4,384 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,384 KB
testcase_06 AC 10 ms
4,376 KB
testcase_07 AC 5 ms
4,380 KB
testcase_08 AC 8 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 5 ms
4,384 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 12 ms
6,068 KB
testcase_13 AC 12 ms
6,132 KB
testcase_14 AC 76 ms
6,000 KB
testcase_15 AC 15 ms
6,696 KB
testcase_16 AC 20 ms
6,996 KB
testcase_17 AC 32 ms
7,552 KB
testcase_18 AC 94 ms
5,724 KB
testcase_19 AC 25 ms
5,188 KB
testcase_20 AC 10 ms
4,596 KB
testcase_21 AC 79 ms
5,292 KB
testcase_22 AC 116 ms
19,960 KB
testcase_23 AC 105 ms
18,480 KB
testcase_24 AC 77 ms
13,652 KB
testcase_25 AC 128 ms
29,728 KB
testcase_26 AC 112 ms
23,684 KB
testcase_27 AC 111 ms
33,472 KB
testcase_28 AC 153 ms
32,088 KB
testcase_29 AC 144 ms
30,672 KB
testcase_30 AC 142 ms
36,340 KB
testcase_31 AC 74 ms
18,416 KB
testcase_32 AC 179 ms
48,996 KB
testcase_33 AC 190 ms
50,688 KB
testcase_34 AC 183 ms
46,580 KB
testcase_35 AC 171 ms
41,612 KB
testcase_36 AC 185 ms
46,088 KB
testcase_37 AC 93 ms
4,376 KB
testcase_38 AC 94 ms
4,380 KB
testcase_39 AC 98 ms
4,376 KB
testcase_40 AC 95 ms
4,380 KB
testcase_41 AC 95 ms
4,376 KB
testcase_42 AC 1 ms
4,380 KB
testcase_43 AC 77 ms
56,352 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