oj.uz

Submission #642137

# Submission time Handle Problem Language Result Execution time Memory
642137 2022-09-18T14:57:30 Z Tenis0206 Brperm (RMI20_brperm) C++17
13 / 100
 480 ms 206832 KB 
#include <bits/stdc++.h>

//#define home

#ifndef home

#include "brperm.h"

#endif // home

using namespace std;

const int Mod = 1e9;
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
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 80 ms 41472 KB Output is correct
4 Correct 95 ms 41480 KB Output is correct
5 Incorrect 91 ms 41548 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 201876 KB Output is correct
2 Incorrect 472 ms 206832 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
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 80 ms 41472 KB Output is correct
4 Correct 95 ms 41480 KB Output is correct
5 Incorrect 91 ms 41548 KB Output isn't correct
6 Halted 0 ms 0 KB -