Submission #1225708
Source Code Expand
#include <bits/stdc++.h> using namespace std; const int MAXSIZE=20000020; const int maxn=500005; 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 | A - Robot Racing |
User | q234rty |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1357 Byte |
Status | RE |
Exec Time | 114 ms |
Memory | 4352 KB |
Judge Result
Set Name | Sample | Subtask | All | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 500 | 0 / 400 | ||||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
Subtask | 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 |
All | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.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, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | WA | 2 ms | 4352 KB |
0_01.txt | RE | 113 ms | 4352 KB |
0_02.txt | WA | 2 ms | 4352 KB |
0_03.txt | WA | 2 ms | 4352 KB |
1_00.txt | RE | 113 ms | 4352 KB |
1_01.txt | RE | 114 ms | 4352 KB |
1_02.txt | RE | 112 ms | 4352 KB |
1_03.txt | WA | 2 ms | 4352 KB |
1_04.txt | WA | 2 ms | 4352 KB |
1_05.txt | RE | 100 ms | 4352 KB |
1_06.txt | WA | 2 ms | 4352 KB |
1_07.txt | WA | 2 ms | 4352 KB |
1_08.txt | RE | 112 ms | 4352 KB |
1_09.txt | WA | 2 ms | 4352 KB |
1_10.txt | RE | 98 ms | 4352 KB |
2_00.txt | WA | 2 ms | 4352 KB |
2_01.txt | WA | 2 ms | 4352 KB |
2_02.txt | RE | 100 ms | 4352 KB |
2_03.txt | WA | 2 ms | 4352 KB |
2_04.txt | WA | 2 ms | 4352 KB |
2_05.txt | WA | 2 ms | 4352 KB |
2_06.txt | WA | 2 ms | 4352 KB |
2_07.txt | WA | 2 ms | 4352 KB |
2_08.txt | WA | 2 ms | 4352 KB |
2_09.txt | WA | 2 ms | 4352 KB |
2_10.txt | WA | 2 ms | 4352 KB |
2_11.txt | RE | 97 ms | 4352 KB |
2_12.txt | RE | 97 ms | 4352 KB |