oj.uz

Submission #1002709

# Submission time Handle Problem Language Result Execution time Memory
1002709 2024-06-19T18:29:37 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
100 / 100
 1604 ms 172836 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++) 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].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:72: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]
   72 |         for(int j = 0; j < t[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 98252 KB Output is correct
2 Correct 878 ms 117816 KB Output is correct
3 Correct 799 ms 113492 KB Output is correct
4 Correct 877 ms 117948 KB Output is correct
5 Correct 800 ms 116456 KB Output is correct
6 Correct 935 ms 120660 KB Output is correct
7 Correct 844 ms 122196 KB Output is correct
8 Correct 825 ms 121684 KB Output is correct
9 Correct 957 ms 119932 KB Output is correct
10 Correct 824 ms 105672 KB Output is correct
11 Correct 844 ms 115748 KB Output is correct
12 Correct 864 ms 108016 KB Output is correct
13 Correct 791 ms 112232 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1046 ms 153520 KB Output is correct
2 Correct 1080 ms 158668 KB Output is correct
3 Correct 1074 ms 154400 KB Output is correct
4 Correct 1048 ms 149580 KB Output is correct
5 Correct 1037 ms 149368 KB Output is correct
6 Correct 1194 ms 158968 KB Output is correct
7 Correct 1068 ms 161248 KB Output is correct
8 Correct 1089 ms 156520 KB Output is correct
9 Correct 1074 ms 159648 KB Output is correct
10 Correct 1249 ms 162732 KB Output is correct
11 Correct 1045 ms 154480 KB Output is correct
12 Correct 992 ms 153000 KB Output is correct
13 Correct 1216 ms 164728 KB Output is correct
14 Correct 1186 ms 162448 KB Output is correct
15 Correct 1029 ms 147592 KB Output is correct
16 Correct 923 ms 160060 KB Output is correct
17 Correct 1040 ms 150228 KB Output is correct
18 Correct 1040 ms 150088 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 98252 KB Output is correct
2 Correct 878 ms 117816 KB Output is correct
3 Correct 799 ms 113492 KB Output is correct
4 Correct 877 ms 117948 KB Output is correct
5 Correct 800 ms 116456 KB Output is correct
6 Correct 935 ms 120660 KB Output is correct
7 Correct 844 ms 122196 KB Output is correct
8 Correct 825 ms 121684 KB Output is correct
9 Correct 957 ms 119932 KB Output is correct
10 Correct 824 ms 105672 KB Output is correct
11 Correct 844 ms 115748 KB Output is correct
12 Correct 864 ms 108016 KB Output is correct
13 Correct 791 ms 112232 KB Output is correct
14 Correct 1046 ms 153520 KB Output is correct
15 Correct 1080 ms 158668 KB Output is correct
16 Correct 1074 ms 154400 KB Output is correct
17 Correct 1048 ms 149580 KB Output is correct
18 Correct 1037 ms 149368 KB Output is correct
19 Correct 1194 ms 158968 KB Output is correct
20 Correct 1068 ms 161248 KB Output is correct
21 Correct 1089 ms 156520 KB Output is correct
22 Correct 1074 ms 159648 KB Output is correct
23 Correct 1249 ms 162732 KB Output is correct
24 Correct 1045 ms 154480 KB Output is correct
25 Correct 992 ms 153000 KB Output is correct
26 Correct 1216 ms 164728 KB Output is correct
27 Correct 1186 ms 162448 KB Output is correct
28 Correct 1029 ms 147592 KB Output is correct
29 Correct 923 ms 160060 KB Output is correct
30 Correct 1040 ms 150228 KB Output is correct
31 Correct 1040 ms 150088 KB Output is correct
32 Correct 1074 ms 136464 KB Output is correct
33 Correct 1179 ms 145600 KB Output is correct
34 Correct 1213 ms 150640 KB Output is correct
35 Correct 1180 ms 148184 KB Output is correct
36 Correct 1209 ms 153280 KB Output is correct
37 Correct 1174 ms 136156 KB Output is correct
38 Correct 1455 ms 169116 KB Output is correct
39 Correct 1438 ms 159380 KB Output is correct
40 Correct 1594 ms 171844 KB Output is correct
41 Correct 1604 ms 172836 KB Output is correct
42 Correct 1537 ms 163916 KB Output is correct
43 Correct 1085 ms 131144 KB Output is correct
44 Correct 1014 ms 130116 KB Output is correct
45 Correct 975 ms 129744 KB Output is correct
46 Correct 1073 ms 137216 KB Output is correct
47 Correct 1379 ms 154432 KB Output is correct
48 Correct 1412 ms 160936 KB Output is correct
49 Correct 1419 ms 155284 KB Output is correct
50 Correct 1477 ms 170696 KB Output is correct
51 Correct 1151 ms 151788 KB Output is correct
52 Correct 916 ms 155488 KB Output is correct
53 Correct 1071 ms 152256 KB Output is correct