oj.uz

Submission #632699

# Submission time Handle Problem Language Result Execution time Memory
632699 2022-08-20T16:10:20 Z AA_Surely Dabbeh (INOI20_dabbeh) C++14
25 / 100
 2000 ms 136700 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, 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 20 ms 32084 KB Output is correct
2 Correct 1347 ms 70092 KB Output is correct
3 Correct 1216 ms 59716 KB Output is correct
4 Correct 1610 ms 71012 KB Output is correct
5 Correct 1491 ms 67860 KB Output is correct
6 Correct 1815 ms 79536 KB Output is correct
7 Correct 1728 ms 81392 KB Output is correct
8 Correct 1710 ms 82864 KB Output is correct
9 Correct 1563 ms 76152 KB Output is correct
10 Correct 943 ms 45788 KB Output is correct
11 Correct 1364 ms 77252 KB Output is correct
12 Correct 962 ms 54780 KB Output is correct
13 Correct 1211 ms 67148 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 32084 KB Output is correct
2 Correct 1347 ms 70092 KB Output is correct
3 Correct 1216 ms 59716 KB Output is correct
4 Correct 1610 ms 71012 KB Output is correct
5 Correct 1491 ms 67860 KB Output is correct
6 Correct 1815 ms 79536 KB Output is correct
7 Correct 1728 ms 81392 KB Output is correct
8 Correct 1710 ms 82864 KB Output is correct
9 Correct 1563 ms 76152 KB Output is correct
10 Correct 943 ms 45788 KB Output is correct
11 Correct 1364 ms 77252 KB Output is correct
12 Correct 962 ms 54780 KB Output is correct
13 Correct 1211 ms 67148 KB Output is correct
14 Execution timed out 2075 ms 136700 KB Time limit exceeded
15 Halted 0 ms 0 KB -