oj.uz

Submission #1094858

# Submission time Handle Problem Language Result Execution time Memory
1094858 2024-09-30T17:04:46 Z alexdd Brperm (RMI20_brperm) C++17
100 / 100
 458 ms 168016 KB 
#include "brperm.h"
#include <bits/stdc++.h>
using namespace std;
int n;
const long long MOD = 1e9+9;
long long p[530005],invp[530005];
long long put(long long a, long long exp)
{
    if(exp==0)
        return 1;
    if(exp%2==0)
        return put(a*a%MOD,exp/2);
    else
        return put(a*a%MOD,exp/2)*a%MOD;
}
int rev(int x, int k)
{
    int aux=0;
    for(int i=0;i<k;i++)
        if(((1<<i)&x))
            aux += (1<<(k-i-1));
    return aux;
}
long long hsh[500005][19];
long long normal[500005][19];
long long sump[500005];
void init(int copn, const char s[])
{
    n=copn;
    p[0]=1;
    p[1]=31;
    for(int i=2;i<=(1<<19);i++)
        p[i] = (p[i-1]*p[1])%MOD;
    for(int i=0;i<=(1<<19);i++)
        invp[i] = put(p[i],MOD-2);

    for(int i=0;i<n;i++)
    {
        hsh[i][0] = normal[i][0] = s[i];
    }
    for(int k=1;k<19;k++)
    {
        for(int i=0;i+(1<<k)-1<n;i++)
        {
            hsh[i][k] = (hsh[i][k-1] + hsh[i+(1<<(k-1))][k-1]*p[(1<<(18-k))])%MOD;

            //for(int j=0;j<(1<<k);j++) normal[i][k] = (normal[i][k] + s[i+j]*p[j*(1<<(18-k))])%MOD;

        }
        long long pref=0;
        long long prod=1;
        for(int i=0;i<n;i++)
        {
            pref = (pref + 1LL*s[i]*prod)%MOD;
            sump[i] = pref;
            prod = prod*p[(1<<(18-k))]%MOD;
        }
        prod=1;
        for(int i=0;i+(1<<k)-1<n;i++)
        {
            normal[i][k] = sump[i+(1<<k)-1];
            if(i>0) normal[i][k] = (normal[i][k] + MOD - sump[i-1])%MOD;
            normal[i][k] = normal[i][k]*prod%MOD;
            prod = prod * invp[(1<<(18-k))]%MOD;
        }
    }
}

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

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 8784 KB Output is correct
2 Correct 95 ms 8764 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 8784 KB Output is correct
2 Correct 95 ms 8764 KB Output is correct
3 Correct 145 ms 40276 KB Output is correct
4 Correct 148 ms 40272 KB Output is correct
5 Correct 148 ms 40272 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 168016 KB Output is correct
2 Correct 458 ms 167760 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 8784 KB Output is correct
2 Correct 95 ms 8764 KB Output is correct
3 Correct 145 ms 40276 KB Output is correct
4 Correct 148 ms 40272 KB Output is correct
5 Correct 148 ms 40272 KB Output is correct
6 Correct 440 ms 168016 KB Output is correct
7 Correct 458 ms 167760 KB Output is correct
8 Correct 443 ms 167672 KB Output is correct
9 Correct 444 ms 167508 KB Output is correct
10 Correct 447 ms 167592 KB Output is correct