oj.uz

Submission #1002699

# Submission time Handle Problem Language Result Execution time Memory
1002699 2024-06-19T18:20:51 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
100 / 100
 1589 ms 178952 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(1.5 * 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 907 ms 98384 KB Output is correct
2 Correct 975 ms 117624 KB Output is correct
3 Correct 888 ms 113424 KB Output is correct
4 Correct 935 ms 117840 KB Output is correct
5 Correct 917 ms 116512 KB Output is correct
6 Correct 907 ms 120540 KB Output is correct
7 Correct 956 ms 122128 KB Output is correct
8 Correct 935 ms 121680 KB Output is correct
9 Correct 942 ms 119888 KB Output is correct
10 Correct 939 ms 105640 KB Output is correct
11 Correct 962 ms 115688 KB Output is correct
12 Correct 757 ms 108064 KB Output is correct
13 Correct 852 ms 112184 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1026 ms 160524 KB Output is correct
2 Correct 1146 ms 165680 KB Output is correct
3 Correct 989 ms 161488 KB Output is correct
4 Correct 1014 ms 156520 KB Output is correct
5 Correct 1006 ms 156500 KB Output is correct
6 Correct 1134 ms 165968 KB Output is correct
7 Correct 1144 ms 168320 KB Output is correct
8 Correct 978 ms 163712 KB Output is correct
9 Correct 1041 ms 166784 KB Output is correct
10 Correct 1080 ms 169828 KB Output is correct
11 Correct 1104 ms 161548 KB Output is correct
12 Correct 1126 ms 160164 KB Output is correct
13 Correct 1133 ms 171904 KB Output is correct
14 Correct 1063 ms 169472 KB Output is correct
15 Correct 1047 ms 154500 KB Output is correct
16 Correct 872 ms 166992 KB Output is correct
17 Correct 842 ms 157240 KB Output is correct
18 Correct 896 ms 157100 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 907 ms 98384 KB Output is correct
2 Correct 975 ms 117624 KB Output is correct
3 Correct 888 ms 113424 KB Output is correct
4 Correct 935 ms 117840 KB Output is correct
5 Correct 917 ms 116512 KB Output is correct
6 Correct 907 ms 120540 KB Output is correct
7 Correct 956 ms 122128 KB Output is correct
8 Correct 935 ms 121680 KB Output is correct
9 Correct 942 ms 119888 KB Output is correct
10 Correct 939 ms 105640 KB Output is correct
11 Correct 962 ms 115688 KB Output is correct
12 Correct 757 ms 108064 KB Output is correct
13 Correct 852 ms 112184 KB Output is correct
14 Correct 1026 ms 160524 KB Output is correct
15 Correct 1146 ms 165680 KB Output is correct
16 Correct 989 ms 161488 KB Output is correct
17 Correct 1014 ms 156520 KB Output is correct
18 Correct 1006 ms 156500 KB Output is correct
19 Correct 1134 ms 165968 KB Output is correct
20 Correct 1144 ms 168320 KB Output is correct
21 Correct 978 ms 163712 KB Output is correct
22 Correct 1041 ms 166784 KB Output is correct
23 Correct 1080 ms 169828 KB Output is correct
24 Correct 1104 ms 161548 KB Output is correct
25 Correct 1126 ms 160164 KB Output is correct
26 Correct 1133 ms 171904 KB Output is correct
27 Correct 1063 ms 169472 KB Output is correct
28 Correct 1047 ms 154500 KB Output is correct
29 Correct 872 ms 166992 KB Output is correct
30 Correct 842 ms 157240 KB Output is correct
31 Correct 896 ms 157100 KB Output is correct
32 Correct 1018 ms 141200 KB Output is correct
33 Correct 1122 ms 150456 KB Output is correct
34 Correct 1075 ms 155384 KB Output is correct
35 Correct 1136 ms 152796 KB Output is correct
36 Correct 1105 ms 157884 KB Output is correct
37 Correct 1020 ms 140820 KB Output is correct
38 Correct 1470 ms 175844 KB Output is correct
39 Correct 1414 ms 166652 KB Output is correct
40 Correct 1373 ms 178176 KB Output is correct
41 Correct 1355 ms 178952 KB Output is correct
42 Correct 1287 ms 170216 KB Output is correct
43 Correct 1186 ms 132892 KB Output is correct
44 Correct 1135 ms 132020 KB Output is correct
45 Correct 1199 ms 131788 KB Output is correct
46 Correct 1216 ms 139412 KB Output is correct
47 Correct 1420 ms 161660 KB Output is correct
48 Correct 1471 ms 167992 KB Output is correct
49 Correct 1494 ms 162392 KB Output is correct
50 Correct 1589 ms 177616 KB Output is correct
51 Correct 1030 ms 158960 KB Output is correct
52 Correct 1159 ms 162352 KB Output is correct
53 Correct 972 ms 159284 KB Output is correct