Submission #3093707


Source Code Expand

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <set>
#include <list>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)

using namespace std;

int i,j,k,l,m,n;
/////////////////////////////////////////////////////
#define INF 999999999
#define DUB 19 //log2_505050

char s[505050];
int Q;

int sl;
int nextc[505050][30];
int nextdb[DUB][505050];


int main(){
    //文字列入力
    cin>>s;

    //データ作成
    for(sl=0;s[sl]!='\0';sl++);

    //cout<<sl<<" "<<endl;
    for(j=0;j<27;j++){
        nextc[sl][j]=INF;
    }

    for(i=sl-1;i>=0;i--){
        for(j=0;j<27;j++){
            nextc[i][j]=INF;
        }
        char cc='z'-s[i]+1;
        nextc[i][cc]=i+1;
        int ci=nextc[nextc[i][cc]][cc];
        
        while(ci!=INF&&cc>0){
            cc--;
            nextc[i][cc]=ci;
            ci=nextc[nextc[i][cc]][cc];
        }
        if(cc==0){
            int idx=nextc[i][0];
            cc='z'-'a'+1;
            while(cc>'z'-s[i]+1){
                ci=nextc[idx][cc];
                nextc[i][cc]=ci;
                cc--;
            }
            nextc[i]['z'-s[nextc[i][0]]+1]=nextc[i][0]+1;
        }
        /*
        cout<<"\n"<<i<<":"<<endl;
        for(j=0;j<27;j++){
            if(nextc[i][j]==INF)
                cout<< " ["<<j<< "]:-"; 
            else
                cout <<" ["<<j<< "]:" << nextc[i][j];
        }
        */
        
    }

    //ダブリング
    for(i=0;i<=sl;i++){
        nextdb[0][i]=nextc[i][0];
    }
    for(k=1;k<DUB;k++){
        for(i=0;i<sl;i++){
            if(nextdb[k-1][i]!=INF){
                nextdb[k][i]=nextdb[k-1][nextdb[k-1][i]];
            }else{
                nextdb[k][i]=INF;
            }
            //cout<<" "<<k<<":"<<i<< nextdb[k][i]<<endl;
        }
    }   

    //検索
    cin>>Q;
    int l,r,lr,next;
    for(i=0;i<Q;i++){
        cin >> l >> r;
        l--;
        for(k=DUB-1;k>=0;k--){
            if(r>=nextdb[k][l]){
                l=nextdb[k][l];
                if(r==l)
                    break;
            }
        }
        if(l==r){
            cout<< "Yes"<<endl;
        }else{
            cout<<"No"<< endl;
        }
    }
    
    return 0;
}

Submission Info

Submission Time
Task C - Robot and String
User hig98ingro
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2404 Byte
Status WA
Exec Time 372 ms
Memory 97408 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1300
Status
AC × 2
WA × 1
AC × 7
WA × 60
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt
Case Name Status Exec Time Memory
0_00.txt AC 8 ms 37120 KB
0_01.txt AC 8 ms 37120 KB
0_02.txt WA 8 ms 37120 KB
1_00.txt AC 214 ms 37376 KB
1_01.txt AC 211 ms 37376 KB
1_02.txt AC 361 ms 97280 KB
1_03.txt AC 353 ms 97280 KB
1_04.txt WA 372 ms 97280 KB
1_05.txt WA 348 ms 97280 KB
1_06.txt WA 331 ms 97280 KB
1_07.txt WA 332 ms 97280 KB
1_08.txt WA 314 ms 97408 KB
1_09.txt WA 315 ms 97280 KB
1_10.txt WA 318 ms 97280 KB
1_11.txt WA 315 ms 97280 KB
1_12.txt WA 322 ms 97280 KB
1_13.txt WA 318 ms 97280 KB
1_14.txt WA 318 ms 97280 KB
1_15.txt WA 313 ms 97280 KB
1_16.txt WA 319 ms 97280 KB
1_17.txt WA 318 ms 97280 KB
1_18.txt WA 318 ms 97280 KB
1_19.txt WA 321 ms 97280 KB
1_20.txt WA 315 ms 97280 KB
1_21.txt WA 318 ms 97280 KB
1_22.txt WA 317 ms 97280 KB
1_23.txt WA 317 ms 97280 KB
1_24.txt WA 319 ms 97280 KB
1_25.txt WA 325 ms 97280 KB
1_26.txt WA 320 ms 97280 KB
1_27.txt WA 328 ms 97280 KB
1_28.txt WA 332 ms 97280 KB
1_29.txt WA 335 ms 97280 KB
1_30.txt WA 326 ms 97280 KB
1_31.txt WA 326 ms 97280 KB
1_32.txt WA 334 ms 97280 KB
1_33.txt WA 309 ms 97280 KB
1_34.txt WA 312 ms 97280 KB
1_35.txt WA 326 ms 97280 KB
1_36.txt WA 332 ms 95104 KB
1_37.txt WA 322 ms 97280 KB
1_38.txt WA 328 ms 97280 KB
1_39.txt WA 333 ms 97280 KB
1_40.txt WA 333 ms 97280 KB
1_41.txt WA 333 ms 97280 KB
1_42.txt WA 331 ms 97152 KB
1_43.txt WA 331 ms 97280 KB
1_44.txt WA 331 ms 97280 KB
1_45.txt WA 333 ms 97280 KB
1_46.txt WA 335 ms 97280 KB
1_47.txt WA 331 ms 97280 KB
1_48.txt WA 331 ms 97280 KB
1_49.txt WA 347 ms 97280 KB
1_50.txt WA 338 ms 97280 KB
1_51.txt WA 328 ms 97280 KB
1_52.txt WA 337 ms 97280 KB
1_53.txt AC 319 ms 97280 KB
1_54.txt WA 327 ms 97280 KB
1_55.txt WA 338 ms 97280 KB
1_56.txt WA 343 ms 97280 KB
1_57.txt WA 329 ms 97280 KB
1_58.txt WA 323 ms 97280 KB
1_59.txt WA 325 ms 97280 KB
1_60.txt WA 313 ms 97280 KB
1_61.txt WA 326 ms 97408 KB
1_62.txt WA 309 ms 97280 KB
1_63.txt WA 324 ms 97280 KB