Submission #632036

#	Time	Username	Problem	Language	Result	Execution time	Memory
632036		AA_Surely	Dabbeh (INOI20_dabbeh)	C++14	50 / 100	2087 ms	197024 KiB

Main

#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];
unordered_set<LL> 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.F * MOD + h.S);
    }

    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 LL getH(int l, int r) {
    if (!l) return hsh[0][r] * MOD + hsh[1][r];
    return ((hsh[0][r] - (hsh[0][l - 1] * pw[0][r - l + 1] % MOD) + 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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 0 / 50