Submission #1225702


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int MAXSIZE=20000020;
const int maxn=500001;
int bufpos;
char buf[MAXSIZE];
void init(){
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=(buf[bufpos]=='-'))?1:0;
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
char s[maxn];
int f[maxn][30],dp[maxn][30];
int main(){
	init();
	int n=readstr(s+1);
	for(int i=1;i<=n;i++)
		s[i]-='a';
	for(int i=n;i;i--){
		f[i][s[i]]=i+1;
		for(int j=s[i]+1;j<=26;j++)
			f[i][j]=f[f[i][j-1]][j-1];
		for(int j=0;j<s[i];j++)
			f[i][j]=f[f[i][26]][j];
	}
	for(int i=n;i;i--){
		dp[i][0]=f[i][26];
		for(int j=1;j<=20;j++)
			dp[i][j]=dp[dp[i][j-1]][j-1];
	}
	int q=readint();
	while(q--){
		int l=readint(),r=readint();
		for(int i=20;i>=0;i--)
			if (dp[l][i]<=r+1 && dp[l][i])
				l=dp[l][i];
		if (l==r+1)
			puts("YES");
		else puts("NO");
	}
}

Submission Info

Submission Time
Task C - Robot and String
User q234rty
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1356 Byte
Status RE
Exec Time 159 ms
Memory 123520 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1300
Status
WA × 3
WA × 28
RE × 39
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 WA 2 ms 6400 KB
0_01.txt WA 2 ms 6400 KB
0_02.txt WA 2 ms 6400 KB
1_00.txt WA 13 ms 6656 KB
1_01.txt WA 13 ms 6656 KB
1_02.txt WA 145 ms 123392 KB
1_03.txt RE 99 ms 6400 KB
1_04.txt RE 98 ms 6400 KB
1_05.txt RE 99 ms 6400 KB
1_06.txt RE 99 ms 6400 KB
1_07.txt RE 101 ms 6400 KB
1_08.txt RE 99 ms 6400 KB
1_09.txt RE 98 ms 6400 KB
1_10.txt RE 98 ms 6400 KB
1_11.txt RE 99 ms 6400 KB
1_12.txt RE 99 ms 6400 KB
1_13.txt RE 100 ms 6400 KB
1_14.txt RE 101 ms 6400 KB
1_15.txt RE 101 ms 6400 KB
1_16.txt RE 99 ms 6400 KB
1_17.txt RE 98 ms 6400 KB
1_18.txt RE 100 ms 6400 KB
1_19.txt RE 100 ms 6400 KB
1_20.txt RE 98 ms 6400 KB
1_21.txt RE 99 ms 6400 KB
1_22.txt RE 99 ms 6400 KB
1_23.txt RE 100 ms 6400 KB
1_24.txt RE 100 ms 6400 KB
1_25.txt RE 98 ms 6400 KB
1_26.txt RE 98 ms 6400 KB
1_27.txt RE 101 ms 6400 KB
1_28.txt RE 98 ms 6400 KB
1_29.txt RE 100 ms 6400 KB
1_30.txt RE 99 ms 6400 KB
1_31.txt RE 99 ms 6400 KB
1_32.txt RE 98 ms 6400 KB
1_33.txt WA 111 ms 123520 KB
1_34.txt WA 97 ms 123392 KB
1_35.txt WA 99 ms 123392 KB
1_36.txt WA 98 ms 123392 KB
1_37.txt WA 101 ms 123392 KB
1_38.txt WA 104 ms 123392 KB
1_39.txt WA 108 ms 123392 KB
1_40.txt WA 108 ms 123392 KB
1_41.txt WA 119 ms 123392 KB
1_42.txt WA 116 ms 123392 KB
1_43.txt WA 119 ms 123392 KB
1_44.txt WA 118 ms 123392 KB
1_45.txt WA 120 ms 123392 KB
1_46.txt WA 126 ms 123392 KB
1_47.txt WA 124 ms 123520 KB
1_48.txt WA 137 ms 123520 KB
1_49.txt WA 144 ms 123520 KB
1_50.txt WA 159 ms 123520 KB
1_51.txt WA 123 ms 123392 KB
1_52.txt WA 144 ms 123520 KB
1_53.txt WA 123 ms 123392 KB
1_54.txt RE 99 ms 6400 KB
1_55.txt RE 99 ms 6400 KB
1_56.txt RE 99 ms 6400 KB
1_57.txt RE 98 ms 6400 KB
1_58.txt RE 99 ms 6400 KB
1_59.txt RE 99 ms 6400 KB
1_60.txt RE 100 ms 6400 KB
1_61.txt RE 98 ms 6400 KB
1_62.txt RE 99 ms 6400 KB
1_63.txt WA 125 ms 123520 KB