oj.uz

Submission #924288

# Submission time Handle Problem Language Result Execution time Memory
924288 2024-02-08T19:28:55 Z Camillus Brperm (RMI20_brperm) C++17
100 / 100
 1248 ms 85072 KB 
#define debug(...) 42
#include "bits/stdc++.h"
using namespace std;

#ifndef LOCAL
#include "brperm.h"
#else
void init(int n, const char s[]);
int query(int i, int k);
#endif

struct mint {
    static constexpr int mod = 998'244'353;
    int value = 0;

    mint() = default;
    mint(int value) : value(value) {}

    mint& operator+=(const mint &other) {
        value += other.value;
        if (value >= mod) {
            value -= mod;
        }
        return *this;
    }

    mint operator+(const mint &other) const {
        mint result = *this;
        return result += other;
    }

    mint& operator-=(const mint &other) {
        value += mod - other.value;
        if (value >= mod) {
            value -= mod;
        }
        return *this;
    }

    mint operator-(const mint &other) const {
        mint result = *this;
        return result -= other;
    }

    mint& operator*=(const mint &other) {
        value = 1ll * value * other.value % mod;
        return *this;
    }

    mint operator*(const mint &other) const {
        mint result = *this;
        return result *= other;
    }

    mint power(int k) const {
        mint result = 1;
        mint current = *this;

        while (k) {
            if (k & 1) {
                result *= current;
            }
            current *= current;
            k >>= 1;
        }

        return result;
    }

    mint& operator/=(const mint &other) {
        return this->operator*=(other.power(mod - 2));
    }

    mint operator/(const mint &other) const {
        mint result = *this;
        return result /= other;
    }

    bool operator==(const mint &other) const {
        return value == other.value;
    } 
};

mint P[21];

mint A[21][500500];
mint B[21][500500];

int n;


void init(int N, const char S[]) {
    n = N;
    for (int i = 0; i <= 20; i++) {
        P[i] = mint(31).power(1 << (23 - i));
    }

    for (int i = 0; i < N; i++) {
        A[0][i] = P[0] * (S[i] - 'a' + 1);
    }

    for (int j = 1; j <= 20; j++) {
        for (int i = 0; i + (1 << j) <= N; i++) {
            A[j][i] = A[j - 1][i] + A[j - 1][i + (1 << (j - 1))] * P[j];
        }
    }

    for (int j = 0; j <= 20; j++) {
        for (int i = 0; i < N; i++) {
            if (i > 0) {
                B[j][i] = B[j][i - 1];
            }

            B[j][i] += P[j].power(i) * (S[i] - 'a' + 1);
        }
    }
}

mint getA(int i, int k) {
    return A[k][i];
}

mint getB(int i, int k) {
    int l = i;
    int r = i + (1 << k) - 1;

    if (l == 0) {
        return B[k][r];
    } else {
        return (B[k][r] - B[k][l - 1]) / P[k].power(l);
    }
}

int query(int i, int k) {
    if (i + (1 << k) > n) {
        return 0;
    }
    return getB(i, k) == getA(i, k);
}

#ifdef LOCAL
char __s[(int)5e5 + 10] = {};

int main() {
    cin >> __s;
    init(strlen(__s), __s);

    int __x, __y;
    while (cin >> __x >> __y)
        cout << query(__x, __y) << '\n';

    return 0;
}
#endif

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct
3 Correct 223 ms 48192 KB Output is correct
4 Correct 224 ms 48208 KB Output is correct
5 Correct 216 ms 48196 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1182 ms 80304 KB Output is correct
2 Correct 1196 ms 85072 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct
3 Correct 223 ms 48192 KB Output is correct
4 Correct 224 ms 48208 KB Output is correct
5 Correct 216 ms 48196 KB Output is correct
6 Correct 1182 ms 80304 KB Output is correct
7 Correct 1196 ms 85072 KB Output is correct
8 Correct 1209 ms 84828 KB Output is correct
9 Correct 1248 ms 84828 KB Output is correct
10 Correct 1209 ms 85048 KB Output is correct