oj.uz

Submission #642144

# Submission time Handle Problem Language Result Execution time Memory
642144 2022-09-18T15:01:49 Z Tenis0206 Brperm (RMI20_brperm) C++17
100 / 100
 487 ms 206880 KB 
#include <bits/stdc++.h>

//#define home

#ifndef home

#include "brperm.h"

#endif // home

using namespace std;

const int Mod = 1e9 + 7;
const int b = 27;

int n;
char c[500005];

long long put[500005];
long long hr[500005][25];
long long h[500005][25];

int lg = 0;

long long lgput(int x, int y)
{
    long long p = 1;
    while(y)
    {
        if(y % 2 == 0)
        {
            y /= 2;
            x = 1LL * x * x % Mod;
        }
        else
        {
            --y;
            p = 1LL * p * x % Mod;
        }
    }
    return p;
}

void build_hr()
{
    for(int i=1;i<=n;i++)
    {
        hr[i][0] = (c[i] - 'a' + 1);
    }
    for(int k=1;k<=lg;k++)
    {
        for(int i=1;i<=n;i++)
        {
            if(i + (1<<k) - 1 > n)
            {
                break;
            }
            hr[i][k] = 1LL * (1LL * put[(1<<(lg-k))] * hr[i][k-1] + hr[i + (1<<(k-1))][k-1]) % Mod;
        }
    }
}

void build_h()
{
    for(int k=0;k<=lg;k++)
    {
        for(int i=1;i<=n;i++)
        {
            h[i][k] = (1LL * h[i-1][k] * put[(1<<k)] + c[i] - 'a' + 1) % Mod;
        }
    }
}

int get_hash(int st, int k)
{
    int p = lg - k;
    int dr = st + (1<<k) - 1;
    return (h[dr][p] - 1LL * h[st-1][p] * lgput(b, (1LL<<p) * (dr - st + 1)) % Mod + Mod) % Mod;
}

void init(int N, const char s[])
{
    n = N;
    put[0] = 1;
    for(int i=1;i<=n;i++)
    {
        put[i] = 1LL * put[i-1] * b % Mod;
    }
    for(int i=1;i<=n;i++)
    {
        c[i] = s[i-1];
    }
    int nr = 1;
    while(nr<=n)
    {
        ++lg;
        nr = 2 * nr;
    }
    --lg;
    build_hr();
    build_h();
}

int query(int poz, int k)
{
    if(poz + (1<<k) - 1 > n)
    {
        return 0;
    }
    ++poz;
    return (hr[poz][k]==get_hash(poz,k));
}

#ifdef home

int nn,qq;
char ss[500005];

signed main()
{
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    cin>>nn;
    for(int i=0;i<nn;i++)
    {
        cin>>ss[i];
    }
    init(nn,ss);
    cin>>qq;
    for(int i=1;i<=qq;i++)
    {
        int poz,k;
        cin>>poz>>k;
        cout<<query(poz,k)<<'\n';
    }
    return 0;
}

#endif // home

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 81 ms 40656 KB Output is correct
4 Correct 78 ms 40572 KB Output is correct
5 Correct 89 ms 40588 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 201880 KB Output is correct
2 Correct 466 ms 201868 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 81 ms 40656 KB Output is correct
4 Correct 78 ms 40572 KB Output is correct
5 Correct 89 ms 40588 KB Output is correct
6 Correct 467 ms 201880 KB Output is correct
7 Correct 466 ms 201868 KB Output is correct
8 Correct 480 ms 206828 KB Output is correct
9 Correct 472 ms 206748 KB Output is correct
10 Correct 487 ms 206880 KB Output is correct