oj.uz

Submission #631925

# Submission time Handle Problem Language Result Execution time Memory
631925 2022-08-19T07:28:06 Z AA_Surely Dabbeh (INOI20_dabbeh) C++14
25 / 100
 1594 ms 146388 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 decond
#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 = 313;
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[L], pw[L];
unordered_set<int> 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) {
    LL h = 0;
    F0R(i, (int)ts[id].length()) {
        h = (h * B + ts[id][i]) % MOD;
        keep[i + 1].insert(h);
    }

    return;
}

void mainHash() {
    hsh[0] = s[0];
    pw[0] = 1;

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

    return;
}

inline LL getH(int l, int r) {
    if (!l) return hsh[r];
    return (hsh[r] - (hsh[l - 1] * pw[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 25 ms 43476 KB Output is correct
2 Correct 411 ms 60880 KB Output is correct
3 Correct 515 ms 56464 KB Output is correct
4 Correct 554 ms 60564 KB Output is correct
5 Correct 558 ms 59036 KB Output is correct
6 Correct 627 ms 63136 KB Output is correct
7 Correct 569 ms 66864 KB Output is correct
8 Correct 608 ms 64476 KB Output is correct
9 Correct 572 ms 62312 KB Output is correct
10 Correct 411 ms 48724 KB Output is correct
11 Correct 357 ms 105752 KB Output is correct
12 Correct 321 ms 73140 KB Output is correct
13 Correct 348 ms 91348 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1488 ms 140092 KB Output is correct
2 Incorrect 1594 ms 146388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 43476 KB Output is correct
2 Correct 411 ms 60880 KB Output is correct
3 Correct 515 ms 56464 KB Output is correct
4 Correct 554 ms 60564 KB Output is correct
5 Correct 558 ms 59036 KB Output is correct
6 Correct 627 ms 63136 KB Output is correct
7 Correct 569 ms 66864 KB Output is correct
8 Correct 608 ms 64476 KB Output is correct
9 Correct 572 ms 62312 KB Output is correct
10 Correct 411 ms 48724 KB Output is correct
11 Correct 357 ms 105752 KB Output is correct
12 Correct 321 ms 73140 KB Output is correct
13 Correct 348 ms 91348 KB Output is correct
14 Correct 1488 ms 140092 KB Output is correct
15 Incorrect 1594 ms 146388 KB Output isn't correct
16 Halted 0 ms 0 KB -