oj.uz

Submission #746406

# Submission time Handle Problem Language Result Execution time Memory
746406 2023-05-22T12:31:01 Z doowey Brperm (RMI20_brperm) C++14
13 / 100
 1480 ms 262144 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 K = 19;
const int B = 77;
vector<char> S;
map<pii, int> dp[N];
int pwr[N];

int make(int i, int step, int lim){
    if(dp[i][mp(step, lim)] != 0) return dp[i][mp(step, lim)];
    if(step == lim){
        //cout << i << " ";
        return S[i] - 'a' + 1;
    }
    int lef, rig;
    lef = make(i, step + 1, lim);
    rig = make(i + (1 << step), step + 1, lim);
    //cout << "merge: " << lef << " + " << rig << "\n";
    lef += (rig * 1ll * pwr[(1<<(lim-step - 1))]) % MOD;
    if(lef >= MOD) lef -= MOD;
    return dp[i][mp(step,lim)]=lef;
}

int H[N][K];

int make2(int i, int step){
    if(H[i][step] != 0) return H[i][step];
    if(step == 0){
        return S[i] - 'a' + 1;
    }
    int lef = make2(i, step - 1);
    int rig = make2(i + (1 << (step - 1)), step - 1);
    lef += (rig * 1ll * pwr[(1 << (step - 1))]) % MOD;
    if(lef >= MOD) lef -= MOD;
    return H[i][step] = lef;
}

void init(int n, const char s[]) {
    pwr[0] = 1;
    for(int i = 1; i <= n; i ++ ) pwr[i] = (pwr[i - 1] * 1ll * B) % MOD;
    for(int i = 0 ; i < n; i ++ ){
        S.push_back(s[i]);
    }
}

int query(int i, int k) {
    if(i + (1 << k) - 1 >= S.size()) return 0;
    int ca = make(i, 0, k);
    int cb = make2(i, k);
    //cout << ca << " " << cb << " |\n";
    return (ca==cb);
}

Compilation message

brperm.cpp: In function 'int query(int, int)':
brperm.cpp:59:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     if(i + (1 << k) - 1 >= S.size()) return 0;
      |        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24788 KB Output is correct
2 Correct 16 ms 24788 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24788 KB Output is correct
2 Correct 16 ms 24788 KB Output is correct
3 Runtime error 1480 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 590 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24788 KB Output is correct
2 Correct 16 ms 24788 KB Output is correct
3 Runtime error 1480 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -