oj.uz

Submission #596605

# Submission time Handle Problem Language Result Execution time Memory
596605 2022-07-14T21:34:42 Z CaroLinda Brperm (RMI20_brperm) C++14
0 / 100
 225 ms 231440 KB 
#include "brperm.h"
#include <bits/stdc++.h>

#define all(x) (x.begin(),x.end())
#define ll long long

const ll PRIME = 37LL;
const ll MOD = 1e9+7;
const int LOG = 20;
const int MAXN = 5e5+10;

using namespace std;

int dp[LOG][MAXN];
ll invPot[LOG][MAXN], sv[LOG][MAXN], pot2[LOG][LOG];
int token;
int N;

ll expo(ll b, ll e){
  if(e == 0)
    return 1LL;

  ll aux = expo(b, e>>1LL);
  aux = (aux*aux) % MOD;

  if(e&1){
    aux = (aux*b) % MOD;
  }

  return aux;
}

void init(int n, const char s[]) {

  N = n;

  for(int i = 0; i < n; i++)
    dp[0][i] = s[i]-'a'+1;

  token = 0;
  while((1<<token) <= n)
    token++;

  token--;

  pot2[0][0] = PRIME;
  for(int i = 1; i <= token; i++)
    pot2[i][0] = (pot2[i-1][0]*pot2[i-1][0])%MOD;

  for(int i = 0; i <= token; i++){
    for(int j = 1; j < LOG; j++)
      pot2[i][j] = (pot2[i][j-1] * pot2[i][0]) % MOD;
  }

  for(int i = 0; i < LOG; i++){
    for(int j= n-1; j >= 0; j--){
      sv[i][j] = sv[i][j+1]*pot2[i][0];
      sv[i][j] %= MOD;
      sv[i][j] += s[j]-'a'+1;
    }
  }

  for(int i = 1; i <= token; i++)
    for(int j= 0; j+(1<<i)-1 < N; j++){
      dp[i][j] = dp[i-1][j];
      ll toSum = dp[i-1][j+(1<<(i-1))]*pot2[token-i][0];
      toSum %= MOD;
      dp[i][j] += toSum;
      if(dp[i][j] >= MOD)
        dp[i][j] -= MOD;
    }

}

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

    ll hashSeq = sv[token-k][l]-(sv[token-k][r+1]*pot2[token-k][r-l])%MOD;
    hashSeq %= MOD;
    hashSeq += MOD;
    hashSeq %= MOD;

    return hashSeq == dp[k][l];
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 225 ms 231440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -