oj.uz

Submission #1002710

# Submission time Handle Problem Language Result Execution time Memory
1002710 2024-06-19T18:29:47 Z TheSahib Dabbeh (INOI20_dabbeh) C++14
100 / 100
 1420 ms 188900 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define ll long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define oo 1e9
const ll MAX = 5e5 + 5, B = 61, MOD = (1ll << 61) - 1, LOGMAX = 18;

struct ST{
    pii tree[4 * MAX];
    void init(){
        for(int i = 0; i < 4 * MAX; i++) tree[i] = {0, 0};
    }
    void update(int node, int l, int r, int pos, pii val){
        if(l == r){
            tree[node] = val;
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid) update(2 * node, l, mid, pos, val);
        else update(2 * node + 1, mid + 1, r, pos, val);
        tree[node] = max(tree[2 * node], tree[2 * node + 1]);
    }
    pii ask(int node, int l, int r, int ql, int qr){
        if(qr < l || r < ql) return {0, 0};
        if(ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return max(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
    }
};
ll binpow(ll a, ll b){
    if(b == 0) return 1;
    if(b & 1) return (__int128_t)binpow(a, b - 1) % MOD * a % MOD;
    return binpow((__int128_t)a * a % MOD, b / 2) % MOD;
}
ll inv(ll a){
    return binpow(a, MOD - 2);
}
int n, q;
string s;
string t[MAX];
 
ll pre[MAX];
ll P[(int)5e5 + 5];
ll invP[(int)5e5 + 5];
int par[LOGMAX][MAX];
int nxt[MAX];
ST st;
unordered_set<ll> mp[MAX];
 
int calc(int l, int r){
    return (__int128_t)(pre[r] - pre[l - 1] + MOD) % MOD * invP[l - 1] % MOD;
}
 
int sz[MAX];
 
void solve(){
    P[0]= 1;
    invP[0] = 1;
    for(int i = 1; i <= 5e5; i++){
        P[i] = (__int128_t)P[i - 1] * B % MOD;
        invP[i] = (__int128_t)invP[i - 1] * inv(B) % MOD;
    }
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> t[i];
        ll H = 0;
        for(int j = 0; j < t[i].size(); j++){
            H = (__int128_t)(H + (__int128_t)(t[i][j] - 'a' + 1) * P[j] % MOD) % MOD;
            mp[j + 1].insert(H);
        }
    }
    cin >> s;
    n = s.size();
    for(int i = 1; i <= n; i++){
        pre[i] = (__int128_t)(pre[i - 1] + (__int128_t)(s[i - 1] - 'a' + 1) * P[i - 1] % MOD) % MOD;
    }
    st.init();
    st.update(1, 1, n + 1, n + 1, {n + 1, n + 1});
    par[0][n + 1] = n + 1;
    nxt[n + 1] = n + 1;
    for(int i = n; i >= 1; i--){
        if(!mp[1].count(calc(i, i))){
            par[0][i] = i;
            nxt[i] = i;
            st.update(1, 1, n + 1, i, {i, i});
            continue;
        }
        int l = i, r = n;
        while(l < r){
            int mid = (l + r + 1) / 2;
            if(mp[mid - i + 1].count(calc(i, mid))) l = mid;
            else r = mid - 1;
        }
        par[0][i] = st.ask(1, 1, n + 1, i + 1, l + 1).second;
        nxt[i] = l + 1;
        st.update(1, 1, n + 1, i, {l + 1, i});
    }
    for(int j = 1; j < LOGMAX; j++){
        for(int i = 1; i <= n + 1; i++){
            par[j][i] = par[j - 1][par[j - 1][i]];
        }
    }
    while(q--){
        int l, r; cin >> l >> r;
        l++;
        if(nxt[l] > r){
            cout << "1\n";
            continue;
        }
        ll ans = 0;
        for(int i = LOGMAX - 1; i >= 0; i--){
            if(nxt[par[i][l]] <= r){
                ans += (1ll << i);
                l = par[i][l];
            }
        }
        if(nxt[par[0][l]] <= r) cout << "-1\n";
        else cout << ans + 2 << '\n';
    }
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while(t--){
        solve();
    }
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:71:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j = 0; j < t[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 82600 KB Output is correct
2 Correct 814 ms 100120 KB Output is correct
3 Correct 797 ms 95724 KB Output is correct
4 Correct 862 ms 99664 KB Output is correct
5 Correct 794 ms 98128 KB Output is correct
6 Correct 848 ms 102412 KB Output is correct
7 Correct 806 ms 106060 KB Output is correct
8 Correct 825 ms 103572 KB Output is correct
9 Correct 771 ms 101432 KB Output is correct
10 Correct 775 ms 87892 KB Output is correct
11 Correct 778 ms 144868 KB Output is correct
12 Correct 745 ms 112444 KB Output is correct
13 Correct 757 ms 130444 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 947 ms 137392 KB Output is correct
2 Correct 1032 ms 142544 KB Output is correct
3 Correct 994 ms 138304 KB Output is correct
4 Correct 909 ms 133564 KB Output is correct
5 Correct 889 ms 133236 KB Output is correct
6 Correct 1014 ms 142992 KB Output is correct
7 Correct 1068 ms 144812 KB Output is correct
8 Correct 1029 ms 140488 KB Output is correct
9 Correct 980 ms 143484 KB Output is correct
10 Correct 1096 ms 146700 KB Output is correct
11 Correct 1027 ms 138404 KB Output is correct
12 Correct 1006 ms 136912 KB Output is correct
13 Correct 1156 ms 148188 KB Output is correct
14 Correct 1042 ms 146184 KB Output is correct
15 Correct 934 ms 131552 KB Output is correct
16 Correct 885 ms 188900 KB Output is correct
17 Correct 889 ms 147776 KB Output is correct
18 Correct 895 ms 147180 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 82600 KB Output is correct
2 Correct 814 ms 100120 KB Output is correct
3 Correct 797 ms 95724 KB Output is correct
4 Correct 862 ms 99664 KB Output is correct
5 Correct 794 ms 98128 KB Output is correct
6 Correct 848 ms 102412 KB Output is correct
7 Correct 806 ms 106060 KB Output is correct
8 Correct 825 ms 103572 KB Output is correct
9 Correct 771 ms 101432 KB Output is correct
10 Correct 775 ms 87892 KB Output is correct
11 Correct 778 ms 144868 KB Output is correct
12 Correct 745 ms 112444 KB Output is correct
13 Correct 757 ms 130444 KB Output is correct
14 Correct 947 ms 137392 KB Output is correct
15 Correct 1032 ms 142544 KB Output is correct
16 Correct 994 ms 138304 KB Output is correct
17 Correct 909 ms 133564 KB Output is correct
18 Correct 889 ms 133236 KB Output is correct
19 Correct 1014 ms 142992 KB Output is correct
20 Correct 1068 ms 144812 KB Output is correct
21 Correct 1029 ms 140488 KB Output is correct
22 Correct 980 ms 143484 KB Output is correct
23 Correct 1096 ms 146700 KB Output is correct
24 Correct 1027 ms 138404 KB Output is correct
25 Correct 1006 ms 136912 KB Output is correct
26 Correct 1156 ms 148188 KB Output is correct
27 Correct 1042 ms 146184 KB Output is correct
28 Correct 934 ms 131552 KB Output is correct
29 Correct 885 ms 188900 KB Output is correct
30 Correct 889 ms 147776 KB Output is correct
31 Correct 895 ms 147180 KB Output is correct
32 Correct 977 ms 118344 KB Output is correct
33 Correct 1125 ms 126788 KB Output is correct
34 Correct 1152 ms 131988 KB Output is correct
35 Correct 1154 ms 129840 KB Output is correct
36 Correct 1138 ms 134832 KB Output is correct
37 Correct 1037 ms 117612 KB Output is correct
38 Correct 1420 ms 149068 KB Output is correct
39 Correct 1260 ms 139336 KB Output is correct
40 Correct 1320 ms 152280 KB Output is correct
41 Correct 1239 ms 155016 KB Output is correct
42 Correct 1397 ms 146708 KB Output is correct
43 Correct 968 ms 113744 KB Output is correct
44 Correct 920 ms 112836 KB Output is correct
45 Correct 958 ms 110280 KB Output is correct
46 Correct 985 ms 117796 KB Output is correct
47 Correct 1179 ms 134692 KB Output is correct
48 Correct 1212 ms 142932 KB Output is correct
49 Correct 1258 ms 137652 KB Output is correct
50 Correct 1332 ms 152688 KB Output is correct
51 Correct 940 ms 138944 KB Output is correct
52 Correct 902 ms 151420 KB Output is correct
53 Correct 925 ms 138056 KB Output is correct