oj.uz

Submission #632033

# Submission time Handle Problem Language Result Execution time Memory
632033 2022-08-19T10:31:21 Z AA_Surely Dabbeh (INOI20_dabbeh) C++14
25 / 100
 2000 ms 148012 KB 
#include <bits/stdc++.h>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int L = 3e5 + 2;
const int N = 5e5 + 2;
const int M = 5e5 + 2;
const int LOG = 20;
const int B[2] = {313, 131};
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;

#define endl '\n'
#define lc now << 1
#define rc now << 1 | 1

int q, m, n;
LL tmp[L];
LL hsh[2][L], pw[2][L];
set<PII> keep[M];
string ts[N], s;

struct IntMaxSeg {
    int tree[N << 2];

    int build(int now = 1, int ls = 0, int rs = n) {
        if (ls == rs) return tree[now] = tmp[ls];
        int mid = (ls + rs) >> 1;
        return tree[now] = max(build(lc, ls, mid), build(rc, mid + 1, rs));
    }

    int get(int lq, int rq, int now = 1, int ls = 0, int rs = n) {
        if (rq < lq || rq < ls || rs < lq) return 0;
        if (lq <= ls && rs <= rq) return tree[now];
        int mid = (ls + rs) >> 1;
        return max(get(lq, rq, lc, ls, mid), get(lq, rq, rc, mid + 1, rs));
    }
} dp[LOG];

void init() {
    cin >> q >> m;
    F0R(i, q) cin >> ts[i];

    cin >> s;
    n = s.length();
}

void calcHash(int id) {
    PLL h = {0, 0};
    F0R(i, (int)ts[id].length()) {
        h.F = (h.F * B[0] + ts[id][i]) % MOD;
        h.S = (h.S * B[1] + ts[id][i]) % MOD;
        keep[i + 1].insert(h);
    }

    return;
}

void mainHash() {

    F0R(k, 2) {
        hsh[k][0] = s[0];
        pw[k][0] = 1;

        FOR(i, 1, n) {
            hsh[k][i] = (hsh[k][i - 1] * B[k] + s[i]) % MOD;
            pw[k][i] = pw[k][i - 1] * B[k] % MOD;
        }
    }

    return;
}

inline PLL getH(int l, int r) {
    if (!l) return {hsh[0][r], hsh[1][r]};
    return {(hsh[0][r] - (hsh[0][l - 1] * pw[0][r - l + 1] % MOD) + MOD) % MOD, 
            (hsh[1][r] - (hsh[1][l - 1] * pw[1][r - l + 1] % MOD) + MOD) % MOD};
}

void dpBase() {
    F0R(i, n + 1) {
        int l = i, r = n, mid;
        while(l < r) {
            mid = (l + r) >> 1;
            if (keep[mid - i + 1].count(getH(i, mid))) l = mid + 1;
            else r = mid;
        }

        tmp[i] = l;
    }

    dp[0].build();
}

void calcLayer(int id) {
    F0R(i, n + 1) {
        int x = dp[id - 1].get(i, i);
        tmp[i] = dp[id - 1].get(i, x);
    }

    dp[id].build();
}

void handleQuery() {
    int l, r; 
    cin >> l >> r;
    r--;

    int now = l, sum = 0;
    if (dp[LOG - 1].get(l, l) <= r) {
        cout << -1 << endl;
        return;
    }

    R0F(i, LOG) {
        int x = dp[i].get(l, now);
        if (x <= r) {
            sum += (1 << i);
            now = x;
        }
    }
    
    cout << sum + 1 << endl;
}

int main() {
    IOS;

    init();

    F0R(i, q) calcHash(i);
    mainHash();
    dpBase();

    FOR(i, 1, LOG) calcLayer(i);
    while(m--) handleQuery();

    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39632 KB Output is correct
2 Correct 438 ms 60056 KB Output is correct
3 Correct 500 ms 55220 KB Output is correct
4 Correct 618 ms 59656 KB Output is correct
5 Correct 608 ms 58124 KB Output is correct
6 Correct 660 ms 62700 KB Output is correct
7 Correct 572 ms 64972 KB Output is correct
8 Correct 648 ms 63576 KB Output is correct
9 Correct 563 ms 61204 KB Output is correct
10 Correct 431 ms 46184 KB Output is correct
11 Correct 326 ms 62648 KB Output is correct
12 Correct 295 ms 51556 KB Output is correct
13 Correct 311 ms 57692 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1835 ms 142028 KB Output is correct
2 Execution timed out 2027 ms 148012 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 39632 KB Output is correct
2 Correct 438 ms 60056 KB Output is correct
3 Correct 500 ms 55220 KB Output is correct
4 Correct 618 ms 59656 KB Output is correct
5 Correct 608 ms 58124 KB Output is correct
6 Correct 660 ms 62700 KB Output is correct
7 Correct 572 ms 64972 KB Output is correct
8 Correct 648 ms 63576 KB Output is correct
9 Correct 563 ms 61204 KB Output is correct
10 Correct 431 ms 46184 KB Output is correct
11 Correct 326 ms 62648 KB Output is correct
12 Correct 295 ms 51556 KB Output is correct
13 Correct 311 ms 57692 KB Output is correct
14 Correct 1835 ms 142028 KB Output is correct
15 Execution timed out 2027 ms 148012 KB Time limit exceeded
16 Halted 0 ms 0 KB -