oj.uz

Submission #632700

# Submission time Handle Problem Language Result Execution time Memory
632700 2022-08-20T16:13:27 Z AA_Surely Dabbeh (INOI20_dabbeh) C++14
25 / 100
 2000 ms 106096 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], mid[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) {
    //cout << "rnk[0][24] rnk[0][25] " << rnk[0][24] << ' ' << rnk[0][25] << endl;
    //cout << "for " << a.F << ' ' << b.F << " rnks are " << rnk[pw - 1][a.F] << ", " << rnk[pw - 1][b.F] << endl;
    //cout << "and pw = " << pw << endl;
    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--;
    }
    /*cout << ns << endl;
    cout <<len << endl;

    cout << "rnk[0] ";
    //F0R(i, len) cout << rnk[0][i] << ' '; cout << endl;
    cout << rnk[0][24] << ' ' << rnk[0][25] << endl;*/

    c = n;
    R0F(i, len) {
        if (ns[i] == C) break;
        p[i].S = c--;
    }
    //cout << rnk[0][24] << ' ' << rnk[0][25] << endl;

    for(pw = 1; pw < LOG; pw++) {
        sort(p, p + len, cmp);
        //cout << rnk[0][24] << ' ' << rnk[0][25] << endl;
        //cout << "after sort ";
        //F0R(i, n) cout << p[i].F << ' '; cout << endl;
        //cout <<"pw = " << pw << endl;

        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]);
            //cout << "cmp(" << p[i - 1].F << ", " << p[i].F << ") = " << cmp(p[i - 1], p[i]) << endl;
        }
        //cout << "rnk ";
        //F0R(i, len) cout << rnk[pw][i] << ' '; cout << endl;
    }
    
    return;
}

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

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

    return ret;
}

void dpBase() {
    int lst = -1;
    F0R(i, len) {
        if (p[i].S < 0) 
            lst = p[i].F;
        if (p[i].S > 0 && lst != -1)
            tmp[ p[i].S - 1 ] = lcp(lst, p[i].F);
    }

    lst = -1;
    R0F(i, len) {
        if (p[i].S < 0) 
            lst = p[i].F;
        if (p[i].S > 0 && lst != -1) 
            tmp[ p[i].S - 1 ] = max(tmp[ p[i].S - 1], lcp(lst, p[i].F));
    }

    /*F0R(i, len) if (p[i].S > 0) F0R(j, len) if (p[j].S < 0) {
        tmp[ p[i].S - 1 ] = max(tmp[ p[i].S - 1 ], lcp(p[i].F, p[j].F));
    }*/

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

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

    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();
    //F0R(i, n + 1) cout << dp[id].get(i, i) << ' '; cout << endl;
}
 
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 1018 ms 36180 KB Output is correct
3 Correct 852 ms 26524 KB Output is correct
4 Correct 1110 ms 36772 KB Output is correct
5 Correct 1091 ms 31588 KB Output is correct
6 Correct 1267 ms 42312 KB Output is correct
7 Correct 1304 ms 44032 KB Output is correct
8 Correct 1333 ms 45256 KB Output is correct
9 Correct 1124 ms 39056 KB Output is correct
10 Correct 546 ms 11652 KB Output is correct
11 Correct 985 ms 40064 KB Output is correct
12 Correct 578 ms 19716 KB Output is correct
13 Correct 789 ms 30924 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 106096 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 852 KB Output is correct
2 Correct 1018 ms 36180 KB Output is correct
3 Correct 852 ms 26524 KB Output is correct
4 Correct 1110 ms 36772 KB Output is correct
5 Correct 1091 ms 31588 KB Output is correct
6 Correct 1267 ms 42312 KB Output is correct
7 Correct 1304 ms 44032 KB Output is correct
8 Correct 1333 ms 45256 KB Output is correct
9 Correct 1124 ms 39056 KB Output is correct
10 Correct 546 ms 11652 KB Output is correct
11 Correct 985 ms 40064 KB Output is correct
12 Correct 578 ms 19716 KB Output is correct
13 Correct 789 ms 30924 KB Output is correct
14 Execution timed out 2081 ms 106096 KB Time limit exceeded
15 Halted 0 ms 0 KB -