oj.uz

Submission #632698

# Submission time Handle Problem Language Result Execution time Memory
632698 2022-08-20T16:09:16 Z AA_Surely Dabbeh (INOI20_dabbeh) C++14
0 / 100
 2000 ms 79492 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 = 1e6 + 7;
const int LOG = 22;
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[N];
int rnk[LOG][N];
PII p[N];
string ts[N], 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, l) {
        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, l) {
        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, n) cout << tmp[i] << ' '; cout << endl;
    //cout << ns << endl;
    //F0R(i, n) cout << p[i].F << ' '; cout << endl;

    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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31992 KB Output is correct
2 Correct 1452 ms 72252 KB Output is correct
3 Correct 1405 ms 62216 KB Output is correct
4 Execution timed out 2079 ms 72916 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31992 KB Output is correct
2 Correct 1452 ms 72252 KB Output is correct
3 Correct 1405 ms 62216 KB Output is correct
4 Execution timed out 2079 ms 72916 KB Time limit exceeded
5 Halted 0 ms 0 KB -