oj.uz

Submission #1002693

# Submission time Handle Problem Language Result Execution time Memory
1002693 2024-06-19T18:15:41 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
100 / 100
 1385 ms 196692 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 = 21;
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_map<ll, int> mp[MAX];
 
int calc(int l, int r){
    return (__int128_t)(pre[r] - pre[l - 1] + MOD) % MOD * invP[l - 1] % MOD;
}
 
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][H] = 1;
        }
    }
    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:68: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]
   68 |         for(int j = 0; j < t[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 82708 KB Output is correct
2 Correct 769 ms 102232 KB Output is correct
3 Correct 721 ms 97876 KB Output is correct
4 Correct 847 ms 101912 KB Output is correct
5 Correct 718 ms 100692 KB Output is correct
6 Correct 759 ms 104676 KB Output is correct
7 Correct 744 ms 108276 KB Output is correct
8 Correct 786 ms 106236 KB Output is correct
9 Correct 781 ms 103844 KB Output is correct
10 Correct 724 ms 90196 KB Output is correct
11 Correct 816 ms 147172 KB Output is correct
12 Correct 725 ms 114536 KB Output is correct
13 Correct 783 ms 132672 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 935 ms 144820 KB Output is correct
2 Correct 929 ms 150220 KB Output is correct
3 Correct 927 ms 145812 KB Output is correct
4 Correct 871 ms 140988 KB Output is correct
5 Correct 880 ms 140696 KB Output is correct
6 Correct 990 ms 150424 KB Output is correct
7 Correct 1016 ms 152624 KB Output is correct
8 Correct 931 ms 148036 KB Output is correct
9 Correct 983 ms 150932 KB Output is correct
10 Correct 1028 ms 154528 KB Output is correct
11 Correct 904 ms 146044 KB Output is correct
12 Correct 997 ms 144332 KB Output is correct
13 Correct 1137 ms 156216 KB Output is correct
14 Correct 1120 ms 154124 KB Output is correct
15 Correct 979 ms 138832 KB Output is correct
16 Correct 990 ms 196692 KB Output is correct
17 Correct 968 ms 155420 KB Output is correct
18 Correct 940 ms 154656 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 82708 KB Output is correct
2 Correct 769 ms 102232 KB Output is correct
3 Correct 721 ms 97876 KB Output is correct
4 Correct 847 ms 101912 KB Output is correct
5 Correct 718 ms 100692 KB Output is correct
6 Correct 759 ms 104676 KB Output is correct
7 Correct 744 ms 108276 KB Output is correct
8 Correct 786 ms 106236 KB Output is correct
9 Correct 781 ms 103844 KB Output is correct
10 Correct 724 ms 90196 KB Output is correct
11 Correct 816 ms 147172 KB Output is correct
12 Correct 725 ms 114536 KB Output is correct
13 Correct 783 ms 132672 KB Output is correct
14 Correct 935 ms 144820 KB Output is correct
15 Correct 929 ms 150220 KB Output is correct
16 Correct 927 ms 145812 KB Output is correct
17 Correct 871 ms 140988 KB Output is correct
18 Correct 880 ms 140696 KB Output is correct
19 Correct 990 ms 150424 KB Output is correct
20 Correct 1016 ms 152624 KB Output is correct
21 Correct 931 ms 148036 KB Output is correct
22 Correct 983 ms 150932 KB Output is correct
23 Correct 1028 ms 154528 KB Output is correct
24 Correct 904 ms 146044 KB Output is correct
25 Correct 997 ms 144332 KB Output is correct
26 Correct 1137 ms 156216 KB Output is correct
27 Correct 1120 ms 154124 KB Output is correct
28 Correct 979 ms 138832 KB Output is correct
29 Correct 990 ms 196692 KB Output is correct
30 Correct 968 ms 155420 KB Output is correct
31 Correct 940 ms 154656 KB Output is correct
32 Correct 1079 ms 125624 KB Output is correct
33 Correct 1158 ms 134656 KB Output is correct
34 Correct 1156 ms 139760 KB Output is correct
35 Correct 1147 ms 137516 KB Output is correct
36 Correct 1111 ms 142740 KB Output is correct
37 Correct 952 ms 125200 KB Output is correct
38 Correct 1347 ms 160700 KB Output is correct
39 Correct 1252 ms 150756 KB Output is correct
40 Correct 1367 ms 163376 KB Output is correct
41 Correct 1284 ms 164136 KB Output is correct
42 Correct 1250 ms 155624 KB Output is correct
43 Correct 941 ms 117980 KB Output is correct
44 Correct 921 ms 117004 KB Output is correct
45 Correct 896 ms 116256 KB Output is correct
46 Correct 978 ms 124200 KB Output is correct
47 Correct 1213 ms 146052 KB Output is correct
48 Correct 1251 ms 152376 KB Output is correct
49 Correct 1211 ms 146724 KB Output is correct
50 Correct 1385 ms 161792 KB Output is correct
51 Correct 950 ms 147784 KB Output is correct
52 Correct 967 ms 162872 KB Output is correct
53 Correct 871 ms 149316 KB Output is correct