Submission #1294393

---

Source Code Expand

#include <cstdio>
#include <algorithm>
static const int MAXN = 5e5 + 4;
static const int LOGN = 20;
static const int ALPHABET = 26;

int n, q;
char s[MAXN];
// f[position][token or ALPHABET - empty string] - first index where the shrunk string equals a given character
int f[MAXN][ALPHABET + 1];
// g[position][power of two] - going 2^i steps through f[*][ALPHABET], the stopping index, or MAXN if nonexistent
int g[MAXN][LOGN];

int main()
{
    for (n = 0; (s[n] = getchar()) != '\n'; ++n) s[n] -= 'a';

    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= ALPHABET; ++j) f[i][j] = g[i][j] = MAXN;
    for (int i = n - 1; i >= 0; --i) {
        f[i][s[i]] = i + 1;
        for (int token = s[i] + 1; token <= ALPHABET; ++token)
            f[i][token] = (f[i][token - 1] == MAXN ? MAXN : f[f[i][token - 1]][token - 1]);
        if (f[i][ALPHABET] != MAXN) for (int token = 0; token < s[i]; ++token)
            f[i][token] = f[f[i][ALPHABET]][token];
        g[i][0] = f[i][ALPHABET];
        for (int j = 1; j < LOGN; ++j)
            g[i][j] = (g[i][j - 1] == MAXN ? MAXN : g[g[i][j - 1]][j - 1]);
    }

    scanf("%d", &q);
    int l, r;
    for (int i = 0; i < q; ++i) {
        scanf("%d%d", &l, &r); --l;
        for (int pot = LOGN - 1; pot >= 0; --pot)
            if (g[l][pot] <= r) l = g[l][pot];
        puts(l == r ? "Yes" : "No");
    }

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:31:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
                    ^
./Main.cpp:34:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &l, &r); --l;
                              ^
./Main.cpp:19:69: warning: iteration 20u invokes undefined behavior [-Waggressive-loop-optimizations]
         for (int j = 0; j <= ALPHABET; ++j) f[i][j] = g[i][j] = MAXN;
                                                                     ^
./Main.cpp:19:27: note: containing loop
         for (int j = 0; j <= ALPHABET; ++j) f[i][j] = g[i][j] = MAXN;
                           ^

Judge Result