oj.uz

Submission #1002713

# Submission time Handle Problem Language Result Execution time Memory
1002713 2024-06-19T18:31:25 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
100 / 100
 1533 ms 168032 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(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].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 813 ms 98388 KB Output is correct
2 Correct 960 ms 115800 KB Output is correct
3 Correct 922 ms 111204 KB Output is correct
4 Correct 957 ms 115348 KB Output is correct
5 Correct 923 ms 114020 KB Output is correct
6 Correct 876 ms 118100 KB Output is correct
7 Correct 1029 ms 119892 KB Output is correct
8 Correct 946 ms 119024 KB Output is correct
9 Correct 933 ms 117156 KB Output is correct
10 Correct 905 ms 103344 KB Output is correct
11 Correct 823 ms 113128 KB Output is correct
12 Correct 751 ms 105696 KB Output is correct
13 Correct 723 ms 109800 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 153024 KB Output is correct
2 Correct 1061 ms 158028 KB Output is correct
3 Correct 973 ms 153820 KB Output is correct
4 Correct 954 ms 149080 KB Output is correct
5 Correct 967 ms 148852 KB Output is correct
6 Correct 1143 ms 158884 KB Output is correct
7 Correct 1090 ms 161128 KB Output is correct
8 Correct 1161 ms 156660 KB Output is correct
9 Correct 1152 ms 159648 KB Output is correct
10 Correct 1203 ms 162580 KB Output is correct
11 Correct 1154 ms 153924 KB Output is correct
12 Correct 1108 ms 152648 KB Output is correct
13 Correct 1153 ms 164568 KB Output is correct
14 Correct 1277 ms 162228 KB Output is correct
15 Correct 1002 ms 147576 KB Output is correct
16 Correct 994 ms 159884 KB Output is correct
17 Correct 907 ms 150304 KB Output is correct
18 Correct 1012 ms 149976 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 98388 KB Output is correct
2 Correct 960 ms 115800 KB Output is correct
3 Correct 922 ms 111204 KB Output is correct
4 Correct 957 ms 115348 KB Output is correct
5 Correct 923 ms 114020 KB Output is correct
6 Correct 876 ms 118100 KB Output is correct
7 Correct 1029 ms 119892 KB Output is correct
8 Correct 946 ms 119024 KB Output is correct
9 Correct 933 ms 117156 KB Output is correct
10 Correct 905 ms 103344 KB Output is correct
11 Correct 823 ms 113128 KB Output is correct
12 Correct 751 ms 105696 KB Output is correct
13 Correct 723 ms 109800 KB Output is correct
14 Correct 912 ms 153024 KB Output is correct
15 Correct 1061 ms 158028 KB Output is correct
16 Correct 973 ms 153820 KB Output is correct
17 Correct 954 ms 149080 KB Output is correct
18 Correct 967 ms 148852 KB Output is correct
19 Correct 1143 ms 158884 KB Output is correct
20 Correct 1090 ms 161128 KB Output is correct
21 Correct 1161 ms 156660 KB Output is correct
22 Correct 1152 ms 159648 KB Output is correct
23 Correct 1203 ms 162580 KB Output is correct
24 Correct 1154 ms 153924 KB Output is correct
25 Correct 1108 ms 152648 KB Output is correct
26 Correct 1153 ms 164568 KB Output is correct
27 Correct 1277 ms 162228 KB Output is correct
28 Correct 1002 ms 147576 KB Output is correct
29 Correct 994 ms 159884 KB Output is correct
30 Correct 907 ms 150304 KB Output is correct
31 Correct 1012 ms 149976 KB Output is correct
32 Correct 1176 ms 135124 KB Output is correct
33 Correct 1190 ms 142612 KB Output is correct
34 Correct 1212 ms 147496 KB Output is correct
35 Correct 1271 ms 145028 KB Output is correct
36 Correct 1230 ms 149936 KB Output is correct
37 Correct 1152 ms 133384 KB Output is correct
38 Correct 1417 ms 164544 KB Output is correct
39 Correct 1398 ms 155068 KB Output is correct
40 Correct 1482 ms 167148 KB Output is correct
41 Correct 1427 ms 168032 KB Output is correct
42 Correct 1533 ms 159512 KB Output is correct
43 Correct 1085 ms 127332 KB Output is correct
44 Correct 1244 ms 126444 KB Output is correct
45 Correct 1076 ms 125984 KB Output is correct
46 Correct 1121 ms 133160 KB Output is correct
47 Correct 1360 ms 150400 KB Output is correct
48 Correct 1223 ms 156476 KB Output is correct
49 Correct 1224 ms 150960 KB Output is correct
50 Correct 1312 ms 166080 KB Output is correct
51 Correct 918 ms 147744 KB Output is correct
52 Correct 934 ms 151100 KB Output is correct
53 Correct 956 ms 147972 KB Output is correct