oj.uz

Submission #632702

# Submission time Handle Problem Language Result Execution time Memory
632702 2022-08-20T16:18:13 Z AA_Surely Dabbeh (INOI20_dabbeh) C++14
25 / 100
 2000 ms 103688 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 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 980 KB Output is correct
2 Correct 1150 ms 37720 KB Output is correct
3 Correct 1006 ms 27584 KB Output is correct
4 Correct 1382 ms 38148 KB Output is correct
5 Correct 1124 ms 33328 KB Output is correct
6 Correct 1335 ms 44160 KB Output is correct
7 Correct 1410 ms 45704 KB Output is correct
8 Correct 1537 ms 47336 KB Output is correct
9 Correct 1278 ms 40820 KB Output is correct
10 Correct 559 ms 12116 KB Output is correct
11 Correct 972 ms 41916 KB Output is correct
12 Correct 593 ms 20532 KB Output is correct
13 Correct 834 ms 32196 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2097 ms 103688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1150 ms 37720 KB Output is correct
3 Correct 1006 ms 27584 KB Output is correct
4 Correct 1382 ms 38148 KB Output is correct
5 Correct 1124 ms 33328 KB Output is correct
6 Correct 1335 ms 44160 KB Output is correct
7 Correct 1410 ms 45704 KB Output is correct
8 Correct 1537 ms 47336 KB Output is correct
9 Correct 1278 ms 40820 KB Output is correct
10 Correct 559 ms 12116 KB Output is correct
11 Correct 972 ms 41916 KB Output is correct
12 Correct 593 ms 20532 KB Output is correct
13 Correct 834 ms 32196 KB Output is correct
14 Execution timed out 2097 ms 103688 KB Time limit exceeded
15 Halted 0 ms 0 KB -