제출 #1280627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280627		AlgorithmWarrior	Brperm (RMI20_brperm)	C++20	100 / 100	321 ms	76264 KiB

brperm

#include <bits/stdc++.h>

using namespace std;

int const BASE=31;
int const MOD=1e9+7;
int const NMAX=500005;
int const LOG=19;
int bexp[LOG];
int hsh[NMAX][LOG];
int dp[NMAX][LOG];
int nn;

void get_bexp(){
    bexp[0]=BASE;
    int i;
    for(i=1;i<LOG;++i)
        bexp[i]=1LL*bexp[i-1]*bexp[i-1]%MOD;
}

void get_hsh(int n,const char s[]){
    int i,j;
    for(j=0;j<LOG;++j){
        hsh[0][j]=s[0]-'a'+1;
        for(i=1;i<n;++i)
            hsh[i][j]=(1LL*hsh[i-1][j]*bexp[j]%MOD+s[i]-'a'+1)%MOD;
    }
}

void get_dp(int n,const char s[]){
    int i,j;
    for(i=0;i<n;++i)
        dp[i][0]=s[i]-'a'+1;
    for(j=1;j<LOG;++j)
        for(i=0;i+(1<<j)<=n;++i)
            dp[i][j]=(1LL*dp[i][j-1]*bexp[LOG-j-1]%MOD+dp[i+(1<<(j-1))][j-1])%MOD;
}

void init(int n,const char s[]){
    nn=n;
    get_bexp();
    get_hsh(n,s);
    get_dp(n,s);
}

int query(int i,int k){
    if(i+(1<<k)-1>=nn)
        return 0;
    int rez1=hsh[i+(1<<k)-1][LOG-k-1];
    if(i)
        rez1=(rez1-1LL*hsh[i-1][LOG-k-1]*bexp[LOG-1]%MOD+MOD)%MOD;
    int rez2=dp[i][k];
    return (rez1==rez2);
}

• Subtask 1: 13 / 13
• Subtask 2: 37 / 37
• Subtask 3: 17 / 17
• Subtask 4: 33 / 33