oj.uz

Submission #854655

# Submission time Handle Problem Language Result Execution time Memory
854655 2023-09-28T10:25:09 Z tibinyte Brperm (RMI20_brperm) C++14
100 / 100
 1121 ms 167460 KB 
#include <bits/stdc++.h>
#include "brperm.h"
using namespace std;
ifstream fin("brperm.in");
ofstream fout("brperm.out");
vector<int> bases = {31,29};
const int mod = 1e9 + 7;
const int lgmax = 18;
const int maxn = 5e5;
struct Mint
{
    int val;
    Mint(int x = 0)
    {
        val = x % mod;
    }
    Mint(long long x)
    {
        val = x % mod;
    }
    Mint operator +(Mint oth)
    {
        return val + oth.val;
    }
    Mint operator -(Mint oth)
    {
        return val - oth.val + mod;
    }
    Mint operator *(Mint oth)
    {
        return 1ll * val * oth.val;
    }
};
Mint powmod(int a, int b)
{
    if(b==0)
    {
        return 1;
    }
    if(b%2==1)
    {
        return powmod(a,b-1) * a;
    }
    Mint P = powmod(a,b/2);
    return P * P;
}
Mint dp[2][lgmax+1][maxn+1];
Mint adam[2][lgmax+1][maxn+1];
Mint hashig[2][maxn+1];
Mint powers[2][maxn+1];
Mint inverses[2][maxn+1];
void init(int n, const char S[])
{
    string s;
    for(int i= 0 ; i < n; ++i)
    {
        s+=S[i];
    }
    s = '$' + s;
    for(int t = 0; t < 2; ++t)
    {
        powers[t][0] = 1;
        for(int i=1; i <=n; ++i)
        {
            powers[t][i] = powers[t][i-1] * bases[t];
        }
        inverses[t][0] = 1;
        Mint invbase = powmod(bases[t],mod-2);
        for(int i= 1; i <=n; ++i)
        {
            inverses[t][i] = inverses[t][i-1] * invbase;
        }
        for(int i = 1; i <=n; ++i)
        {
            hashig[t][i] = hashig[t][i-1] + powers[t][i-1] * (s[i]-'a'+1);
        }
    }
    for(int t = 0; t < 2; ++t)
    {
        for(int i=1; i <=n; ++i)
        {
            for(int j = 0; j <= lgmax; ++j)
            {
                dp[t][j][i] = (s[i]-'a'+1);
            }
            adam[t][0][i] = dp[t][0][i];
        }
        for(int j = 1; j <= lgmax; ++j)
        {
            for(int i = 1; i + (1<<j)-1 <= n; ++i)
            {
                Mint mybase = bases[t];
                for(int k = 0; k <= lgmax - j; ++k)
                {
                    dp[t][k][i] = dp[t][k+1][i] + dp[t][k+1][i+(1<<(j-1))] * mybase;
                    mybase = mybase * mybase;
                }
                adam[t][j][i] = dp[t][0][i];
            }
        }
    }
}
int query(int st, int k)
{
    st++;
    int dr = st+(1<<k)-1;
    for(int t = 0; t < 2; ++t){
        Mint x = (hashig[t][dr] - hashig[t][st-1]) * inverses[t][st-1];
        if(x.val != adam[t][k][st].val){
            return false;
        }
    }
    return true;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 160852 KB Output is correct
2 Correct 20 ms 160852 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 160852 KB Output is correct
2 Correct 20 ms 160852 KB Output is correct
3 Correct 228 ms 162164 KB Output is correct
4 Correct 226 ms 162004 KB Output is correct
5 Correct 228 ms 162100 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 162444 KB Output is correct
2 Correct 1105 ms 167280 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 160852 KB Output is correct
2 Correct 20 ms 160852 KB Output is correct
3 Correct 228 ms 162164 KB Output is correct
4 Correct 226 ms 162004 KB Output is correct
5 Correct 228 ms 162100 KB Output is correct
6 Correct 1102 ms 162444 KB Output is correct
7 Correct 1105 ms 167280 KB Output is correct
8 Correct 1121 ms 167328 KB Output is correct
9 Correct 1109 ms 167460 KB Output is correct
10 Correct 1103 ms 167284 KB Output is correct