Submission #1225709

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int MAXSIZE=20000020;
const int maxn=500003;
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

Judge Result