oj.uz

Submission #632703

# Submission time Handle Problem Language Result Execution time Memory
632703 2022-08-20T16:19:26 Z AA_Surely Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 128476 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#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 N = 3e5 + 7;
const int L = 1e6 + 7;
const int Q = 1e4 + 7;
const int LOG = 20;
const char C = ' ';

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

int q, m, n, pw, len;
int tmp[N], moj[L];
int rnk[LOG][L];
PII p[L];
string ts[Q], s, ns;

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];
        ns += C + ts[i];
    }

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

    ns += C + s;
    len = ns.length();
}

inline bool cmp(const PII &a, const PII &b) {
    if (rnk[pw - 1][a.F] != rnk[pw - 1][b.F]) return (rnk[pw - 1][a.F] < rnk[pw - 1][b.F]);
    if (max(a.F, b.F) + (1 << (pw - 1)) >= len) return (a.F > b.F);
    return (rnk[pw - 1][a.F + (1 << (pw - 1))] < rnk[pw - 1][b.F + (1 << (pw - 1))]);
}

void buildSA() {
    int c = -1;
    F0R(i, len) {
        rnk[0][i] = ns[i];
        p[i].F = i;
        if (i && ns[i - 1] == C) p[i].S = c--;
    }

    c = n;
    R0F(i, len) {
        if (ns[i] == C) break;
        p[i].S = c--;
    }

    for(pw = 1; pw < LOG; pw++) {
        sort(p, p + len, cmp);

        rnk[pw][ p[0].F ] = 0;
        FOR(i, 1, len) rnk[pw][ p[i].F ] = rnk[pw][ p[i - 1].F ] + cmp(p[i - 1], p[i]);
    }
    
    return;
}

inline int lcp(int a, int b) {
    int ret = 0;
    R0F(i, LOG) {
        if (max(a, b) + (1 << i) > len || rnk[i][a] != rnk[i][b]) continue;

        ret |= (1 << i);
        a += (1 << i);
        b += (1 << i);
    }

    return ret;
}

void dpBase() {
    FOR(i, 1, len) moj[i] = lcp(p[i - 1].F, p[i].F);
    int mx = 0;

    FOR(i, 1, len) {
        mx = min(mx, moj[i]);

        if (p[i].S < 0) 
            mx = ts[ -p[i].S - 1 ].length();
        if (p[i].S > 0)
            tmp[ p[i].S - 1 ] = mx;
    }

    mx = 0;
    R0F(i, len) {
        mx = min(mx, moj[i + 1]);
        if (p[i].S < 0) 
            mx = ts[ -p[i].S - 1 ].length();
        if (p[i].S > 0) 
            tmp[ p[i].S - 1 ] = max(tmp[ p[i].S - 1], mx);
    }

    F0R(i, n + 1) tmp[i] += i;
    dp[0].build();

    return;
}

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();
 
    buildSA();
    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 1 ms 852 KB Output is correct
2 Correct 883 ms 37680 KB Output is correct
3 Correct 714 ms 27588 KB Output is correct
4 Correct 915 ms 38192 KB Output is correct
5 Correct 909 ms 33032 KB Output is correct
6 Correct 1043 ms 44116 KB Output is correct
7 Correct 1099 ms 46008 KB Output is correct
8 Correct 1080 ms 47208 KB Output is correct
9 Correct 983 ms 40808 KB Output is correct
10 Correct 483 ms 11976 KB Output is correct
11 Correct 764 ms 41912 KB Output is correct
12 Correct 491 ms 20644 KB Output is correct
13 Correct 686 ms 32332 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1945 ms 128476 KB Output is correct
2 Execution timed out 2071 ms 116796 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 883 ms 37680 KB Output is correct
3 Correct 714 ms 27588 KB Output is correct
4 Correct 915 ms 38192 KB Output is correct
5 Correct 909 ms 33032 KB Output is correct
6 Correct 1043 ms 44116 KB Output is correct
7 Correct 1099 ms 46008 KB Output is correct
8 Correct 1080 ms 47208 KB Output is correct
9 Correct 983 ms 40808 KB Output is correct
10 Correct 483 ms 11976 KB Output is correct
11 Correct 764 ms 41912 KB Output is correct
12 Correct 491 ms 20644 KB Output is correct
13 Correct 686 ms 32332 KB Output is correct
14 Correct 1945 ms 128476 KB Output is correct
15 Execution timed out 2071 ms 116796 KB Time limit exceeded
16 Halted 0 ms 0 KB -