UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213988#2739. 阿空的核聚变KXG402976ms98648kbC++111.2kb2024-11-14 21:33:302024-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;
}

Details

小提示:点击横条可展开更详细的信息

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