oj.uz

Submission #634495

# Submission time Handle Problem Language Result Execution time Memory
634495 2022-08-24T13:27:41 Z MohammadAghil Dabbeh (INOI20_dabbeh) C++17
100 / 100
 817 ms 120968 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define pb push_back
#define ff first
#define ss second

void dbg(){
    cerr << endl;
}
template<typename Head, typename... Tail> void dbg(Head h, Tail... t){
    cerr << " " << h << ",";
    dbg(t...);
}
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">:", dbg(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void IOS(){
    cin.tie(0) -> sync_with_stdio(0);
//    #ifndef ONLINE_JUDGE
//        freopen("inp.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
//    #endif
}

const ll mod = 1e9 + 7, mod2 = 1e9 + 9, maxn = 3e5 + 5, lg = 19, inf = ll(1e9) + 5;

/*
struct C{
    int operator()(pair<int, int> x) const {
        return x.ff^x.ss;
    }
};

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

gp_hash_table<pair<int, int>, bool, C> is;

void add(string s){
    pp hsh = {0, 0};
    for(char c: s){
        hsh.ff = (hsh.ff*p + c - 'a' + 1)%mod;
        hsh.ss = (hsh.ss*p + c - 'a' + 1)%mod2;
        is[hsh] = true;
    }
}

ll pw1[maxn], pw2[maxn];
pp hsh[maxn];

void build_hash(string s){
    rep(i,0,sz(s)){
        hsh[i].ff = ((i?hsh[i-1].ff:0)*p + s[i] - 'a' + 1)%mod;
        hsh[i].ss = ((i?hsh[i-1].ss:0)*p + s[i] - 'a' + 1)%mod2;
    }
    pw1[0] = pw2[0] = 1;
    rep(i,1,sz(s) + 1){
        pw1[i] = pw1[i-1]*p%mod;
        pw2[i] = pw2[i-1]*p%mod2;
    }
}

pair<int, int> get_hsh(int l, int r){
    return {
        (hsh[r].ff - (l?hsh[l-1].ff*pw1[r-l+1]%mod:0) + mod)%mod,
        (hsh[r].ss - (l?hsh[l-1].ss*pw2[r-l+1]%mod2:0) + mod2)%mod2
    };
}

*/
int nxt[maxn][lg], nxt_id[maxn][lg];
pair<int, int> rmq[maxn][lg];
int lgg[maxn], m;

void build_rmq(int x){
    m++;
    rep(i,0,m) rmq[i][0] = {nxt[i][x], i};
    rep(i,2,m + 1) lgg[i] = lgg[i>>1] + 1;
    rep(j,1,lg){
        rep(i,0,m - (1<<j) + 1){
            rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
        }
    }
    m--;
}

pp get_rmq(int l, int r){
    int k = lgg[r - l + 1];
    return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
}

vector<int> SuffixArray(string s){
    s.pb('$');
    int n = sz(s);
    vector<int> p(n), rnk(n), tmp(n), pn(n), cnt(n);
    iota(all(p), 0);
    sort(all(p), [&](int i, int j){return s[i] < s[j];});
    rep(i,1,n){
        rnk[p[i]] = rnk[p[i-1]] + (s[p[i]] != s[p[i-1]]);
    }
    auto get = [&](int i, int k){
        int en = i + (1<<k);
        if(en >= n) en -= n;
        return pp(rnk[i], rnk[en]);
    };
    for(int k = 0; (1 << k) < n; k++){
        rep(i,0,n) {
            pn[i] = p[i] - (1<<k) + n;
            if(pn[i] >= n){
                pn[i] -= n;
                if(pn[i] >= n) pn[i] -= n;
            }
        }
        fill(all(cnt), 0);
        rep(i,0,n) cnt[rnk[i]]++;
        rep(i,1,n) cnt[i] += cnt[i-1];
        per(i,n-1,0) p[--cnt[rnk[pn[i]]]] = pn[i];
        tmp[p[0]] = 0;
        rep(i,1,n) tmp[p[i]] = tmp[p[i-1]] + (get(p[i], k) != get(p[i-1], k));
        rnk.swap(tmp);
    }
    p.erase(begin(p));
    return p;
}

int main(){ IOS();
    int n, q; cin >> n >> q;
    vector<string> t(n);
    rep(i,0,n){
        cin >> t[i];
    }
    string s; cin >> s;
    m = sz(s);

    vector<int> srt = SuffixArray(s);
//    int rr = 0;
//    for(int c: srt){
//        cerr << rr++ << ' ' << string(begin(s) + c, end(s)) << endl;
//    }

    vector<vector<pp>> add(m), rem(m + 1);

    int tmp = 0;
    rep(i,0,n){
        int lx = 0, rx = m, ptr = 0;
        for(char c: t[i]){
            int lx1 = lx-1, rx1 = rx;
            while(lx1 + 1 < rx1){
                int mid = (lx1 + rx1)>>1;
                int en = srt[mid] + ptr;
                if(en >= m || c > s[en]) lx1 = mid;
                else rx1 = mid;
            }
            int lx2 = lx1, rx2 = rx;
            while(lx2 + 1 < rx2){
                int mid = (lx2 + rx2)>>1;
                int en = srt[mid] + ptr;
                if(en >= m || c >= s[en]) lx2 = mid;
                else rx2 = mid;
            }
            if(lx1 == lx2) break;
            ptr++;
            lx = rx1, rx = rx2;
            add[lx].pb({ptr, tmp});
            rem[rx-1].pb({ptr, tmp}); tmp++;
//            er(i, lx, rx-1);
        }
    }

    rep(j,0,lg) nxt[m][j] = nxt_id[m][j] = m;
    vector<bool> is(maxn<<1);
    priority_queue<pp> pq;
    rep(i,0,m){
        for(pp c: add[i]) pq.push(c), is[c.ss] = true;
        while(sz(pq) && !is[pq.top().ss]) pq.pop();
        nxt[srt[i]][0] = srt[i];
        if(sz(pq)) nxt[srt[i]][0] += pq.top().ff;
        for(pp c: rem[i]) is[c.ss] = false;
    }

//    rep(i,0,m) er(i, nxt[i][0]);

    /*
    build_hash(s);

    rep(i,0,m){
        int lx = i-1, rx = m;
        while(lx + 1 < rx){
            int mid = (lx + rx)>>1;
            if(is[get_hsh(i, mid)]) lx = mid;
            else rx = mid;
        }
        nxt[i][0] = rx;
    }
    */

    build_rmq(0);
    rep(i,0,m){
        nxt_id[i][0] = get_rmq(i, nxt[i][0]).ss;
    }
    rep(j,1,lg){
        rep(i,0,m){
            nxt[i][j] = nxt[nxt_id[i][j-1]][j-1], nxt_id[i][j] = nxt_id[nxt_id[i][j-1]][j-1];
        }
    }

    while(q--){
        int l, r; cin >> l >> r; r--;
        if(nxt[l][lg-1] <= r) cout << -1 << '\n';
        else{
            int ans = 0;
            per(i,lg-1,0){
                int nx = nxt[l][i];
                if(nx <= r){
                    ans |= 1<<i;
                    l = nxt_id[l][i];
                }
            }
            cout << ans + 1 << '\n';
        }
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 71 ms 1996 KB Output is correct
3 Correct 78 ms 1948 KB Output is correct
4 Correct 78 ms 2712 KB Output is correct
5 Correct 76 ms 2068 KB Output is correct
6 Correct 78 ms 3092 KB Output is correct
7 Correct 76 ms 2052 KB Output is correct
8 Correct 79 ms 3144 KB Output is correct
9 Correct 75 ms 2296 KB Output is correct
10 Correct 73 ms 1868 KB Output is correct
11 Correct 69 ms 1632 KB Output is correct
12 Correct 63 ms 1312 KB Output is correct
13 Correct 66 ms 1512 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 107400 KB Output is correct
2 Correct 452 ms 108464 KB Output is correct
3 Correct 440 ms 106844 KB Output is correct
4 Correct 433 ms 107856 KB Output is correct
5 Correct 489 ms 108768 KB Output is correct
6 Correct 489 ms 108000 KB Output is correct
7 Correct 470 ms 109356 KB Output is correct
8 Correct 500 ms 108496 KB Output is correct
9 Correct 467 ms 108516 KB Output is correct
10 Correct 397 ms 108352 KB Output is correct
11 Correct 453 ms 107396 KB Output is correct
12 Correct 512 ms 107520 KB Output is correct
13 Correct 454 ms 107448 KB Output is correct
14 Correct 455 ms 107192 KB Output is correct
15 Correct 423 ms 108668 KB Output is correct
16 Correct 379 ms 120968 KB Output is correct
17 Correct 359 ms 113396 KB Output is correct
18 Correct 343 ms 113208 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 71 ms 1996 KB Output is correct
3 Correct 78 ms 1948 KB Output is correct
4 Correct 78 ms 2712 KB Output is correct
5 Correct 76 ms 2068 KB Output is correct
6 Correct 78 ms 3092 KB Output is correct
7 Correct 76 ms 2052 KB Output is correct
8 Correct 79 ms 3144 KB Output is correct
9 Correct 75 ms 2296 KB Output is correct
10 Correct 73 ms 1868 KB Output is correct
11 Correct 69 ms 1632 KB Output is correct
12 Correct 63 ms 1312 KB Output is correct
13 Correct 66 ms 1512 KB Output is correct
14 Correct 493 ms 107400 KB Output is correct
15 Correct 452 ms 108464 KB Output is correct
16 Correct 440 ms 106844 KB Output is correct
17 Correct 433 ms 107856 KB Output is correct
18 Correct 489 ms 108768 KB Output is correct
19 Correct 489 ms 108000 KB Output is correct
20 Correct 470 ms 109356 KB Output is correct
21 Correct 500 ms 108496 KB Output is correct
22 Correct 467 ms 108516 KB Output is correct
23 Correct 397 ms 108352 KB Output is correct
24 Correct 453 ms 107396 KB Output is correct
25 Correct 512 ms 107520 KB Output is correct
26 Correct 454 ms 107448 KB Output is correct
27 Correct 455 ms 107192 KB Output is correct
28 Correct 423 ms 108668 KB Output is correct
29 Correct 379 ms 120968 KB Output is correct
30 Correct 359 ms 113396 KB Output is correct
31 Correct 343 ms 113208 KB Output is correct
32 Correct 536 ms 72284 KB Output is correct
33 Correct 503 ms 73744 KB Output is correct
34 Correct 516 ms 73632 KB Output is correct
35 Correct 469 ms 73532 KB Output is correct
36 Correct 444 ms 72872 KB Output is correct
37 Correct 548 ms 73328 KB Output is correct
38 Correct 816 ms 110004 KB Output is correct
39 Correct 787 ms 109692 KB Output is correct
40 Correct 738 ms 111188 KB Output is correct
41 Correct 723 ms 110244 KB Output is correct
42 Correct 794 ms 108780 KB Output is correct
43 Correct 358 ms 39044 KB Output is correct
44 Correct 355 ms 39304 KB Output is correct
45 Correct 321 ms 37904 KB Output is correct
46 Correct 323 ms 40544 KB Output is correct
47 Correct 817 ms 109092 KB Output is correct
48 Correct 787 ms 109464 KB Output is correct
49 Correct 805 ms 109708 KB Output is correct
50 Correct 810 ms 109096 KB Output is correct
51 Correct 406 ms 109376 KB Output is correct
52 Correct 402 ms 116264 KB Output is correct
53 Correct 402 ms 110016 KB Output is correct