oj.uz

Submission #1002721

# Submission time Handle Problem Language Result Execution time Memory
1002721 2024-06-19T18:36:48 Z TheSahib Dabbeh (INOI20_dabbeh) C++14
100 / 100
 1500 ms 132580 KB 
// #pragma optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;

#define ll long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define oo 1e9

const int MAX = 5e5 + 5, B = 61, LOGMAX = 18;
const ll MOD = (1ll << 61) - 1;

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];
 
ll 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++) sz[t[i].size()]++;
    for(int i = 1; i < MAX; i++) mp[i].reserve(4 * sz[i]);

    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:77:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int j = 0; j < t[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 82548 KB Output is correct
2 Correct 955 ms 102292 KB Output is correct
3 Correct 885 ms 97752 KB Output is correct
4 Correct 908 ms 102160 KB Output is correct
5 Correct 1004 ms 100524 KB Output is correct
6 Correct 867 ms 104696 KB Output is correct
7 Correct 947 ms 106324 KB Output is correct
8 Correct 870 ms 105712 KB Output is correct
9 Correct 855 ms 103852 KB Output is correct
10 Correct 777 ms 89708 KB Output is correct
11 Correct 882 ms 99852 KB Output is correct
12 Correct 794 ms 92128 KB Output is correct
13 Correct 846 ms 96424 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 115380 KB Output is correct
2 Correct 1143 ms 120756 KB Output is correct
3 Correct 1082 ms 116240 KB Output is correct
4 Correct 1104 ms 111516 KB Output is correct
5 Correct 1114 ms 111244 KB Output is correct
6 Correct 1127 ms 120908 KB Output is correct
7 Correct 1102 ms 123164 KB Output is correct
8 Correct 1162 ms 118660 KB Output is correct
9 Correct 1061 ms 121744 KB Output is correct
10 Correct 1045 ms 124696 KB Output is correct
11 Correct 1006 ms 116504 KB Output is correct
12 Correct 1100 ms 115116 KB Output is correct
13 Correct 1110 ms 126524 KB Output is correct
14 Correct 1086 ms 124248 KB Output is correct
15 Correct 873 ms 109560 KB Output is correct
16 Correct 888 ms 121832 KB Output is correct
17 Correct 981 ms 112180 KB Output is correct
18 Correct 813 ms 112048 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 82548 KB Output is correct
2 Correct 955 ms 102292 KB Output is correct
3 Correct 885 ms 97752 KB Output is correct
4 Correct 908 ms 102160 KB Output is correct
5 Correct 1004 ms 100524 KB Output is correct
6 Correct 867 ms 104696 KB Output is correct
7 Correct 947 ms 106324 KB Output is correct
8 Correct 870 ms 105712 KB Output is correct
9 Correct 855 ms 103852 KB Output is correct
10 Correct 777 ms 89708 KB Output is correct
11 Correct 882 ms 99852 KB Output is correct
12 Correct 794 ms 92128 KB Output is correct
13 Correct 846 ms 96424 KB Output is correct
14 Correct 1071 ms 115380 KB Output is correct
15 Correct 1143 ms 120756 KB Output is correct
16 Correct 1082 ms 116240 KB Output is correct
17 Correct 1104 ms 111516 KB Output is correct
18 Correct 1114 ms 111244 KB Output is correct
19 Correct 1127 ms 120908 KB Output is correct
20 Correct 1102 ms 123164 KB Output is correct
21 Correct 1162 ms 118660 KB Output is correct
22 Correct 1061 ms 121744 KB Output is correct
23 Correct 1045 ms 124696 KB Output is correct
24 Correct 1006 ms 116504 KB Output is correct
25 Correct 1100 ms 115116 KB Output is correct
26 Correct 1110 ms 126524 KB Output is correct
27 Correct 1086 ms 124248 KB Output is correct
28 Correct 873 ms 109560 KB Output is correct
29 Correct 888 ms 121832 KB Output is correct
30 Correct 981 ms 112180 KB Output is correct
31 Correct 813 ms 112048 KB Output is correct
32 Correct 1004 ms 103096 KB Output is correct
33 Correct 1148 ms 112116 KB Output is correct
34 Correct 1132 ms 117024 KB Output is correct
35 Correct 1129 ms 114588 KB Output is correct
36 Correct 1068 ms 119572 KB Output is correct
37 Correct 1093 ms 102780 KB Output is correct
38 Correct 1335 ms 126440 KB Output is correct
39 Correct 1187 ms 117080 KB Output is correct
40 Correct 1467 ms 129040 KB Output is correct
41 Correct 1500 ms 132580 KB Output is correct
42 Correct 1297 ms 124100 KB Output is correct
43 Correct 1033 ms 106276 KB Output is correct
44 Correct 990 ms 105260 KB Output is correct
45 Correct 995 ms 104712 KB Output is correct
46 Correct 1063 ms 113308 KB Output is correct
47 Correct 1088 ms 115840 KB Output is correct
48 Correct 1198 ms 122168 KB Output is correct
49 Correct 1164 ms 116908 KB Output is correct
50 Correct 1254 ms 131920 KB Output is correct
51 Correct 999 ms 113148 KB Output is correct
52 Correct 985 ms 116540 KB Output is correct
53 Correct 954 ms 113484 KB Output is correct