oj.uz

Submission #1002718

# Submission time Handle Problem Language Result Execution time Memory
1002718 2024-06-19T18:36:06 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
100 / 100
 1446 ms 134612 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 = 4639, 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];

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(10 * 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: '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 836 ms 82560 KB Output is correct
2 Correct 911 ms 102192 KB Output is correct
3 Correct 835 ms 97840 KB Output is correct
4 Correct 867 ms 102264 KB Output is correct
5 Correct 804 ms 100788 KB Output is correct
6 Correct 883 ms 104984 KB Output is correct
7 Correct 875 ms 106576 KB Output is correct
8 Correct 836 ms 105808 KB Output is correct
9 Correct 770 ms 103700 KB Output is correct
10 Correct 870 ms 89936 KB Output is correct
11 Correct 868 ms 99556 KB Output is correct
12 Correct 790 ms 92228 KB Output is correct
13 Correct 842 ms 96296 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1056 ms 115360 KB Output is correct
2 Correct 1090 ms 120756 KB Output is correct
3 Correct 1066 ms 116376 KB Output is correct
4 Correct 869 ms 111420 KB Output is correct
5 Correct 894 ms 111240 KB Output is correct
6 Correct 1101 ms 121120 KB Output is correct
7 Correct 1040 ms 123360 KB Output is correct
8 Correct 1162 ms 118652 KB Output is correct
9 Correct 1203 ms 121736 KB Output is correct
10 Correct 1259 ms 124908 KB Output is correct
11 Correct 1100 ms 116508 KB Output is correct
12 Correct 1035 ms 115048 KB Output is correct
13 Correct 1163 ms 126872 KB Output is correct
14 Correct 1092 ms 124508 KB Output is correct
15 Correct 1037 ms 109368 KB Output is correct
16 Correct 981 ms 122088 KB Output is correct
17 Correct 801 ms 112180 KB Output is correct
18 Correct 944 ms 112040 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 82560 KB Output is correct
2 Correct 911 ms 102192 KB Output is correct
3 Correct 835 ms 97840 KB Output is correct
4 Correct 867 ms 102264 KB Output is correct
5 Correct 804 ms 100788 KB Output is correct
6 Correct 883 ms 104984 KB Output is correct
7 Correct 875 ms 106576 KB Output is correct
8 Correct 836 ms 105808 KB Output is correct
9 Correct 770 ms 103700 KB Output is correct
10 Correct 870 ms 89936 KB Output is correct
11 Correct 868 ms 99556 KB Output is correct
12 Correct 790 ms 92228 KB Output is correct
13 Correct 842 ms 96296 KB Output is correct
14 Correct 1056 ms 115360 KB Output is correct
15 Correct 1090 ms 120756 KB Output is correct
16 Correct 1066 ms 116376 KB Output is correct
17 Correct 869 ms 111420 KB Output is correct
18 Correct 894 ms 111240 KB Output is correct
19 Correct 1101 ms 121120 KB Output is correct
20 Correct 1040 ms 123360 KB Output is correct
21 Correct 1162 ms 118652 KB Output is correct
22 Correct 1203 ms 121736 KB Output is correct
23 Correct 1259 ms 124908 KB Output is correct
24 Correct 1100 ms 116508 KB Output is correct
25 Correct 1035 ms 115048 KB Output is correct
26 Correct 1163 ms 126872 KB Output is correct
27 Correct 1092 ms 124508 KB Output is correct
28 Correct 1037 ms 109368 KB Output is correct
29 Correct 981 ms 122088 KB Output is correct
30 Correct 801 ms 112180 KB Output is correct
31 Correct 944 ms 112040 KB Output is correct
32 Correct 1002 ms 105796 KB Output is correct
33 Correct 1105 ms 115204 KB Output is correct
34 Correct 1205 ms 119992 KB Output is correct
35 Correct 1154 ms 117672 KB Output is correct
36 Correct 1215 ms 122624 KB Output is correct
37 Correct 1107 ms 105620 KB Output is correct
38 Correct 1408 ms 130964 KB Output is correct
39 Correct 1362 ms 121484 KB Output is correct
40 Correct 1446 ms 133792 KB Output is correct
41 Correct 1376 ms 134612 KB Output is correct
42 Correct 1263 ms 126016 KB Output is correct
43 Correct 1098 ms 107964 KB Output is correct
44 Correct 1034 ms 107080 KB Output is correct
45 Correct 969 ms 106528 KB Output is correct
46 Correct 1082 ms 114036 KB Output is correct
47 Correct 1309 ms 116688 KB Output is correct
48 Correct 1362 ms 122908 KB Output is correct
49 Correct 1322 ms 117328 KB Output is correct
50 Correct 1218 ms 132540 KB Output is correct
51 Correct 1056 ms 113852 KB Output is correct
52 Correct 946 ms 117328 KB Output is correct
53 Correct 1103 ms 114488 KB Output is correct