ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#213988 | #2739. 阿空的核聚变 | KXG | 40 | 2976ms | 98648kb | C++11 | 1.2kb | 2024-11-14 21:33:30 | 2024-11-14 23:08:03 |
answer
#include <cstdio>
#include <cstring>
using namespace std;
char s[500010];
int n, q, l, r, dp[500010][30], nxt[30][500010];
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 0; i <= 26; i++) {
dp[n + 1][i] = n + 1;
}
nxt[0][n + 1] = n + 1;
for (int i = n; i >= 1; i--) {
for (int j = s[i] - 'a'; j <= 26; j++) {
if (s[i] - 'a' == j) {
dp[i][j] = i + 1;
} else {
dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
}
for (int j = 0; j < s[i] - 'a'; j++) {
dp[i][j] = dp[dp[i][26]][j];
}
nxt[0][i] = dp[i][26];
// printf("%d : %d\n", i, nxt[0][i]);
}
for (int i = 1; i < 20; i++) {
for (int j = 1; j <= n + 1; j++) {
nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
}
}
scanf("%d", &q);
while (q--) {
scanf("%d%d", &l, &r);
int now = l;
for (int i = 19; i >= 0; i--) {
if (nxt[i][now] <= r + 1) {
now = nxt[i][now];
}
}
if (now == r + 1) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 612kb
input:
wwwwyyyvttttutsrqquuusstttuvutrrsvvwxvvwvvvvwuuvwvvwwuuurrssswywvvwvurrstxwvvxxxxxxyzvvvssrrsttvuuwy...
output:
No No No No No No No Yes Yes No No No No No No No No No No No No No No No Yes No Yes No No No No No ...
result:
wrong answer 8th lines differ - expected: 'No', found: 'Yes'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 612kb
input:
wvvvvwwttuvwwyyxxwvvwwzywvttuusstuuwyyywwxyywvuttuuuttwxwwyyyxxzzxxxwvuuyyyyzvvvvwvvvvwwwztssuuuwwwy...
output:
No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No ...
result:
wrong answer 18th lines differ - expected: 'No', found: 'Yes'
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 612kb
input:
zywwxyyzyyvuttwvvwxutssvuuvyyzzyxxyxxzzyyxxyxxxxzyxxwuuvwwxwwyxxyvvttuvxyyyxxyyyyyxxyyxwwxxyyyvuuwww...
output:
No No No No No No No No No Yes No No No No No No Yes No No No No No No No No No No No No No No No No...
result:
wrong answer 10th lines differ - expected: 'No', found: 'Yes'
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 1176kb
input:
zzzyywwxyzxxyzyyzzyyyyzyyzyxxzzzzyyyyyxxyyzzyxxzzyyzzzyyzyyzzzzyyyyzzzxwwwwxzzzzyyzxxyyyzzyyyyyyzzzy...
output:
No No No Yes No Yes No No Yes No Yes No No No No No No Yes No No No No No No No No No No Yes No No N...
result:
wrong answer 779th lines differ - expected: 'No', found: 'Yes'
Test #5:
score: 0
Wrong Answer
time: 0ms
memory: 1176kb
input:
yxxyxxzzyyxxyyxxxxxxxwvuuxvvwyyxxxxyyyyxxwwxzyxxyxxyyyxwvuttywvvxxxywwxywwxxwuuuuzxxyxwwxvvwwuuvxyww...
output:
No Yes No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No...
result:
wrong answer 561st lines differ - expected: 'No', found: 'Yes'
Test #6:
score: 0
Wrong Answer
time: 1ms
memory: 1172kb
input:
xxyywvvxyuuuuvvwwxxxttuvvvzvvwwwyyywwsstuuttvvwvttuwvurrrrsqqrxxvvttttvxuuvwvusstvvxwwyxxzzxwwxutsss...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No N...
result:
wrong answer 739th lines differ - expected: 'No', found: 'Yes'
Test #7:
score: 10
Accepted
time: 624ms
memory: 98648kb
input:
yyzzzyyzzzyyzzzzyzzyyzyyzzyzzyzzzzyyzyyzzyzyzyyzyzyzzzzzzyzzyzzzyyyzyyzzyyyzzyzyyzzzyyzyyzzzyzyzyzyy...
output:
No Yes No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No...
result:
ok 1000000 lines
Test #8:
score: 10
Accepted
time: 631ms
memory: 98648kb
input:
yzzzzyzzyyzyzzzyyyzyyzyzzzyzyzzzzzzzyyyzyyzyzzzzyzzyyyyyzyyzyzyyzzzyzzyzzyzzzzzyyzyyyyyzyyyzzyzyzzyy...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No Yes Yes No No N...
result:
ok 1000000 lines
Test #9:
score: 10
Accepted
time: 773ms
memory: 98648kb
input:
yyyyxxyzxxxxxxwvuuvvwzxxwwvuuvuuxutssvutssuttxxyxxxvvttuvxxywwxxwwyywwxyyywwxzyxwwxxywwwwyyyywwxyyvv...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No N...
result:
ok 1000000 lines
Test #10:
score: 10
Accepted
time: 947ms
memory: 98648kb
input:
ywwxyyxxyzzzyxxyyyyzzzzzzyyzzyxxzzyyyxxzzzywwxzzyyzwwxxwwyyzyyzzzyyzyyyxwwyxxyyzyyyxxyyzyxxyyzzywwxw...
output:
No No No No No No No No Yes No No No No No Yes No No Yes No No No Yes No No No No Yes No No No No No...
result:
ok 1000000 lines