oj.uz

Submission #1002654

# Submission time Handle Problem Language Result Execution time Memory
1002654 2024-06-19T17:38:32 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
100 / 100
 1420 ms 136980 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;
 
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[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.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.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 678 ms 55376 KB Output is correct
2 Correct 728 ms 75968 KB Output is correct
3 Correct 777 ms 70212 KB Output is correct
4 Correct 806 ms 76220 KB Output is correct
5 Correct 826 ms 72276 KB Output is correct
6 Correct 794 ms 78360 KB Output is correct
7 Correct 783 ms 80072 KB Output is correct
8 Correct 812 ms 79292 KB Output is correct
9 Correct 850 ms 77500 KB Output is correct
10 Correct 797 ms 62988 KB Output is correct
11 Correct 828 ms 78300 KB Output is correct
12 Correct 772 ms 67848 KB Output is correct
13 Correct 754 ms 71988 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1032 ms 117044 KB Output is correct
2 Correct 1073 ms 122748 KB Output is correct
3 Correct 1025 ms 119164 KB Output is correct
4 Correct 1016 ms 113504 KB Output is correct
5 Correct 1069 ms 113344 KB Output is correct
6 Correct 1079 ms 122740 KB Output is correct
7 Correct 1131 ms 124536 KB Output is correct
8 Correct 983 ms 120784 KB Output is correct
9 Correct 1186 ms 123008 KB Output is correct
10 Correct 1127 ms 128600 KB Output is correct
11 Correct 1018 ms 119308 KB Output is correct
12 Correct 1086 ms 116932 KB Output is correct
13 Correct 1123 ms 129724 KB Output is correct
14 Correct 1138 ms 128152 KB Output is correct
15 Correct 977 ms 111476 KB Output is correct
16 Correct 1041 ms 129572 KB Output is correct
17 Correct 973 ms 115888 KB Output is correct
18 Correct 997 ms 115656 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 55376 KB Output is correct
2 Correct 728 ms 75968 KB Output is correct
3 Correct 777 ms 70212 KB Output is correct
4 Correct 806 ms 76220 KB Output is correct
5 Correct 826 ms 72276 KB Output is correct
6 Correct 794 ms 78360 KB Output is correct
7 Correct 783 ms 80072 KB Output is correct
8 Correct 812 ms 79292 KB Output is correct
9 Correct 850 ms 77500 KB Output is correct
10 Correct 797 ms 62988 KB Output is correct
11 Correct 828 ms 78300 KB Output is correct
12 Correct 772 ms 67848 KB Output is correct
13 Correct 754 ms 71988 KB Output is correct
14 Correct 1032 ms 117044 KB Output is correct
15 Correct 1073 ms 122748 KB Output is correct
16 Correct 1025 ms 119164 KB Output is correct
17 Correct 1016 ms 113504 KB Output is correct
18 Correct 1069 ms 113344 KB Output is correct
19 Correct 1079 ms 122740 KB Output is correct
20 Correct 1131 ms 124536 KB Output is correct
21 Correct 983 ms 120784 KB Output is correct
22 Correct 1186 ms 123008 KB Output is correct
23 Correct 1127 ms 128600 KB Output is correct
24 Correct 1018 ms 119308 KB Output is correct
25 Correct 1086 ms 116932 KB Output is correct
26 Correct 1123 ms 129724 KB Output is correct
27 Correct 1138 ms 128152 KB Output is correct
28 Correct 977 ms 111476 KB Output is correct
29 Correct 1041 ms 129572 KB Output is correct
30 Correct 973 ms 115888 KB Output is correct
31 Correct 997 ms 115656 KB Output is correct
32 Correct 1028 ms 98440 KB Output is correct
33 Correct 1169 ms 107204 KB Output is correct
34 Correct 1115 ms 113600 KB Output is correct
35 Correct 1177 ms 109036 KB Output is correct
36 Correct 1177 ms 115812 KB Output is correct
37 Correct 1010 ms 97976 KB Output is correct
38 Correct 1397 ms 134520 KB Output is correct
39 Correct 1350 ms 123156 KB Output is correct
40 Correct 1383 ms 136640 KB Output is correct
41 Correct 1420 ms 136980 KB Output is correct
42 Correct 1369 ms 127860 KB Output is correct
43 Correct 933 ms 90236 KB Output is correct
44 Correct 957 ms 89724 KB Output is correct
45 Correct 930 ms 89200 KB Output is correct
46 Correct 926 ms 97668 KB Output is correct
47 Correct 1230 ms 118612 KB Output is correct
48 Correct 1194 ms 125564 KB Output is correct
49 Correct 1244 ms 118984 KB Output is correct
50 Correct 1306 ms 135612 KB Output is correct
51 Correct 976 ms 116236 KB Output is correct
52 Correct 954 ms 121276 KB Output is correct
53 Correct 966 ms 117088 KB Output is correct