oj.uz

Submission #746982

# Submission time Handle Problem Language Result Execution time Memory
746982 2023-05-23T10:40:52 Z doowey Brperm (RMI20_brperm) C++14
100 / 100
 345 ms 83580 KB 
#include <bits/stdc++.h>
#include "brperm.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int MOD = (int)1e9 + 9;
const int N = (int)5e5 + 10;
const int B = 77;
const int K = 20;
const int M = (1 << K) + 1;
int pwr[M];
int F[K][N];
int G[K][N];

int powr(int m, int k){
    if(k == 0) return 1;
    int p = powr(m, k / 2);
    p = (p * 1ll * p) % MOD;
    if(k % 2 == 1) p = (p * 1ll * m) % MOD;
    return p;
}

int mult(int x, int y){
    return (x * 1ll * y) % MOD;
}

int add(int x, int y){
    x += y;
    if(x >= MOD) x -= MOD;
    else if(x < 0) x += MOD;
    return x;
}

int n;

void init(int _n, const char s[]) {
    pwr[0] = 1;
    n = _n;
    for(int i = 1; i <= (1 << K); i ++ ){
        pwr[i] = (pwr[i - 1] * 1ll * B) % MOD;
    }
    int chum;
    for(int i = 0 ; i < K; i ++ ){
        if((1 << i) <= n){
            chum = 0;
            for(int j = n - 1; j >= 0 ; j -- ){
                chum = mult(chum, pwr[(1 << (K - i))]);
                chum = add(chum, s[j] - 'a' + 1);
                F[i][j] = chum;
            }
            if(i == 0){
                for(int j = 0 ; j < n; j ++ ){
                    G[i][j] = s[j] - 'a' + 1;
                }
            }
            else{
                for(int j = 0; j + (1 << i) - 1 < n; j ++ ){
                    G[i][j] = add(G[i - 1][j], mult(G[i - 1][j + (1 << (i - 1))], pwr[(1 << (K - i))]));
                }
            }
        }
    }
}

int calcF(int i, int k){
    return add(F[k][i],-mult(F[k][i+(1<<k)],powr(pwr[(1<<(K-k))], (1 << k))));
}

int query(int i, int k) {
    if(i + (1 << k) - 1 >= n) return 0;
    return (G[k][i] == calcF(i, k));
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4564 KB Output is correct
2 Correct 9 ms 4564 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4564 KB Output is correct
2 Correct 9 ms 4564 KB Output is correct
3 Correct 68 ms 18572 KB Output is correct
4 Correct 67 ms 18548 KB Output is correct
5 Correct 72 ms 18572 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 83580 KB Output is correct
2 Correct 345 ms 83144 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4564 KB Output is correct
2 Correct 9 ms 4564 KB Output is correct
3 Correct 68 ms 18572 KB Output is correct
4 Correct 67 ms 18548 KB Output is correct
5 Correct 72 ms 18572 KB Output is correct
6 Correct 322 ms 83580 KB Output is correct
7 Correct 345 ms 83144 KB Output is correct
8 Correct 345 ms 83256 KB Output is correct
9 Correct 333 ms 83232 KB Output is correct
10 Correct 345 ms 83200 KB Output is correct