oj.uz

Submission #631879

# Submission time Handle Problem Language Result Execution time Memory
631879 2022-08-19T04:49:19 Z AA_Surely Dabbeh (INOI20_dabbeh) C++17
0 / 100
 1451 ms 140004 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 N = 3e5 + 2;
const int LOG = 20;
const int B = 313;
const int MOD = 998'244'353;
const int INF = 1e9 + 7;

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

int q, m, n;
int tmp[N];
LL hsh[N], pw[N];
string ts[N], s;
unordered_set<int> keep[N];

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));
        //cout << now << " tree[" << ls << ", " << rs << "] = " << tree[now] << endl;
        //return tree[now];
    }

    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);
        //cout << "keep[" << i + 1 << "].insert " << h << endl;
    }

    return;
}

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

    FOR(i, 1, n) {
        hsh[i] = (hsh[i - 1] * B + s[i]) % MOD;
        //cout << "hsh[" << i << "] = " << hsh[i] << endl;
        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() {
    //cout <<"getH(" << 0 << ", " << 1 << ") = " << getH(0, 1) << endl;
    F0R(i, n + 1) {
        int l = i, r = n + 1, 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;
    }

    //F0R(i, n + 1) cout << tmp[i] << ' '; cout << endl;
    dp[0].build();

    //cout << "done the base -------------------------------------------_" << endl;
}

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();
    //F0R(i, n + 1) cout << tmp[i] << ' '; cout << endl;
}

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

    int now = l;
    int ans = INF, sum = 0;

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

    cout << (ans == INF ? -1 : ans) << endl;
}

int main() {
    IOS;

    init();

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


    FOR(i, 1, LOG) calcLayer(i);
    //cout << dp[1].get(0, 0) << endl;
    while(m--) handleQuery();

    return 0;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26324 KB Output is correct
2 Correct 361 ms 45748 KB Output is correct
3 Correct 432 ms 41696 KB Output is correct
4 Correct 513 ms 45924 KB Output is correct
5 Correct 510 ms 44440 KB Output is correct
6 Correct 546 ms 48736 KB Output is correct
7 Correct 544 ms 52352 KB Output is correct
8 Correct 539 ms 49940 KB Output is correct
9 Correct 484 ms 47668 KB Output is correct
10 Correct 374 ms 33656 KB Output is correct
11 Runtime error 148 ms 140004 KB Execution killed with signal 8
12 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1451 ms 122144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26324 KB Output is correct
2 Correct 361 ms 45748 KB Output is correct
3 Correct 432 ms 41696 KB Output is correct
4 Correct 513 ms 45924 KB Output is correct
5 Correct 510 ms 44440 KB Output is correct
6 Correct 546 ms 48736 KB Output is correct
7 Correct 544 ms 52352 KB Output is correct
8 Correct 539 ms 49940 KB Output is correct
9 Correct 484 ms 47668 KB Output is correct
10 Correct 374 ms 33656 KB Output is correct
11 Runtime error 148 ms 140004 KB Execution killed with signal 8
12 Halted 0 ms 0 KB -