oj.uz

Submission #1002697

# Submission time Handle Problem Language Result Execution time Memory
1002697 2024-06-19T18:19:12 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
100 / 100
 1403 ms 178976 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;
}

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(3 * 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][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:74: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]
   74 |         for(int j = 0; j < t[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 808 ms 98384 KB Output is correct
2 Correct 887 ms 117836 KB Output is correct
3 Correct 835 ms 113280 KB Output is correct
4 Correct 791 ms 117804 KB Output is correct
5 Correct 866 ms 116304 KB Output is correct
6 Correct 839 ms 120400 KB Output is correct
7 Correct 835 ms 121936 KB Output is correct
8 Correct 842 ms 121300 KB Output is correct
9 Correct 844 ms 119448 KB Output is correct
10 Correct 872 ms 105784 KB Output is correct
11 Correct 715 ms 115432 KB Output is correct
12 Correct 789 ms 107988 KB Output is correct
13 Correct 810 ms 112308 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 906 ms 160588 KB Output is correct
2 Correct 1022 ms 165860 KB Output is correct
3 Correct 1026 ms 161292 KB Output is correct
4 Correct 995 ms 156484 KB Output is correct
5 Correct 968 ms 156536 KB Output is correct
6 Correct 1058 ms 165900 KB Output is correct
7 Correct 1091 ms 168364 KB Output is correct
8 Correct 1068 ms 163716 KB Output is correct
9 Correct 1062 ms 166764 KB Output is correct
10 Correct 1250 ms 169896 KB Output is correct
11 Correct 950 ms 161664 KB Output is correct
12 Correct 939 ms 160176 KB Output is correct
13 Correct 1163 ms 171812 KB Output is correct
14 Correct 990 ms 169376 KB Output is correct
15 Correct 966 ms 154612 KB Output is correct
16 Correct 780 ms 167112 KB Output is correct
17 Correct 811 ms 157352 KB Output is correct
18 Correct 800 ms 157020 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 808 ms 98384 KB Output is correct
2 Correct 887 ms 117836 KB Output is correct
3 Correct 835 ms 113280 KB Output is correct
4 Correct 791 ms 117804 KB Output is correct
5 Correct 866 ms 116304 KB Output is correct
6 Correct 839 ms 120400 KB Output is correct
7 Correct 835 ms 121936 KB Output is correct
8 Correct 842 ms 121300 KB Output is correct
9 Correct 844 ms 119448 KB Output is correct
10 Correct 872 ms 105784 KB Output is correct
11 Correct 715 ms 115432 KB Output is correct
12 Correct 789 ms 107988 KB Output is correct
13 Correct 810 ms 112308 KB Output is correct
14 Correct 906 ms 160588 KB Output is correct
15 Correct 1022 ms 165860 KB Output is correct
16 Correct 1026 ms 161292 KB Output is correct
17 Correct 995 ms 156484 KB Output is correct
18 Correct 968 ms 156536 KB Output is correct
19 Correct 1058 ms 165900 KB Output is correct
20 Correct 1091 ms 168364 KB Output is correct
21 Correct 1068 ms 163716 KB Output is correct
22 Correct 1062 ms 166764 KB Output is correct
23 Correct 1250 ms 169896 KB Output is correct
24 Correct 950 ms 161664 KB Output is correct
25 Correct 939 ms 160176 KB Output is correct
26 Correct 1163 ms 171812 KB Output is correct
27 Correct 990 ms 169376 KB Output is correct
28 Correct 966 ms 154612 KB Output is correct
29 Correct 780 ms 167112 KB Output is correct
30 Correct 811 ms 157352 KB Output is correct
31 Correct 800 ms 157020 KB Output is correct
32 Correct 952 ms 139992 KB Output is correct
33 Correct 1071 ms 150020 KB Output is correct
34 Correct 1062 ms 155104 KB Output is correct
35 Correct 1145 ms 152316 KB Output is correct
36 Correct 1113 ms 157556 KB Output is correct
37 Correct 1088 ms 140316 KB Output is correct
38 Correct 1356 ms 175360 KB Output is correct
39 Correct 1222 ms 164632 KB Output is correct
40 Correct 1403 ms 178112 KB Output is correct
41 Correct 1393 ms 178976 KB Output is correct
42 Correct 1246 ms 170468 KB Output is correct
43 Correct 1056 ms 132756 KB Output is correct
44 Correct 983 ms 131680 KB Output is correct
45 Correct 1000 ms 131360 KB Output is correct
46 Correct 1016 ms 138800 KB Output is correct
47 Correct 1252 ms 160912 KB Output is correct
48 Correct 1182 ms 167224 KB Output is correct
49 Correct 1197 ms 161632 KB Output is correct
50 Correct 1315 ms 176996 KB Output is correct
51 Correct 966 ms 158396 KB Output is correct
52 Correct 968 ms 161784 KB Output is correct
53 Correct 1024 ms 158688 KB Output is correct