oj.uz

Submission #1002701

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 780 ms 78856 KB Output is correct
2 Correct 971 ms 105732 KB Output is correct
3 Correct 966 ms 99412 KB Output is correct
4 Correct 943 ms 105516 KB Output is correct
5 Correct 961 ms 103248 KB Output is correct
6 Correct 1045 ms 109564 KB Output is correct
7 Correct 995 ms 112728 KB Output is correct
8 Correct 1062 ms 111184 KB Output is correct
9 Correct 985 ms 108116 KB Output is correct
10 Correct 861 ms 88144 KB Output is correct
11 Correct 851 ms 109604 KB Output is correct
12 Correct 864 ms 94940 KB Output is correct
13 Correct 839 ms 103140 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1329 ms 144104 KB Output is correct
2 Correct 1432 ms 151756 KB Output is correct
3 Correct 1217 ms 145484 KB Output is correct
4 Correct 1116 ms 138536 KB Output is correct
5 Correct 1125 ms 138352 KB Output is correct
6 Correct 1435 ms 152136 KB Output is correct
7 Correct 1523 ms 155308 KB Output is correct
8 Correct 1389 ms 148608 KB Output is correct
9 Correct 1482 ms 153032 KB Output is correct
10 Correct 1438 ms 157688 KB Output is correct
11 Correct 1382 ms 145744 KB Output is correct
12 Correct 1378 ms 143492 KB Output is correct
13 Correct 1612 ms 160252 KB Output is correct
14 Correct 1365 ms 157272 KB Output is correct
15 Correct 1052 ms 135616 KB Output is correct
16 Correct 879 ms 160520 KB Output is correct
17 Correct 877 ms 141620 KB Output is correct
18 Correct 907 ms 141408 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 780 ms 78856 KB Output is correct
2 Correct 971 ms 105732 KB Output is correct
3 Correct 966 ms 99412 KB Output is correct
4 Correct 943 ms 105516 KB Output is correct
5 Correct 961 ms 103248 KB Output is correct
6 Correct 1045 ms 109564 KB Output is correct
7 Correct 995 ms 112728 KB Output is correct
8 Correct 1062 ms 111184 KB Output is correct
9 Correct 985 ms 108116 KB Output is correct
10 Correct 861 ms 88144 KB Output is correct
11 Correct 851 ms 109604 KB Output is correct
12 Correct 864 ms 94940 KB Output is correct
13 Correct 839 ms 103140 KB Output is correct
14 Correct 1329 ms 144104 KB Output is correct
15 Correct 1432 ms 151756 KB Output is correct
16 Correct 1217 ms 145484 KB Output is correct
17 Correct 1116 ms 138536 KB Output is correct
18 Correct 1125 ms 138352 KB Output is correct
19 Correct 1435 ms 152136 KB Output is correct
20 Correct 1523 ms 155308 KB Output is correct
21 Correct 1389 ms 148608 KB Output is correct
22 Correct 1482 ms 153032 KB Output is correct
23 Correct 1438 ms 157688 KB Output is correct
24 Correct 1382 ms 145744 KB Output is correct
25 Correct 1378 ms 143492 KB Output is correct
26 Correct 1612 ms 160252 KB Output is correct
27 Correct 1365 ms 157272 KB Output is correct
28 Correct 1052 ms 135616 KB Output is correct
29 Correct 879 ms 160520 KB Output is correct
30 Correct 877 ms 141620 KB Output is correct
31 Correct 907 ms 141408 KB Output is correct
32 Correct 1107 ms 122664 KB Output is correct
33 Correct 1351 ms 135876 KB Output is correct
34 Correct 1379 ms 143088 KB Output is correct
35 Correct 1417 ms 139628 KB Output is correct
36 Correct 1358 ms 147140 KB Output is correct
37 Correct 1133 ms 122268 KB Output is correct
38 Correct 1767 ms 164328 KB Output is correct
39 Correct 1642 ms 150344 KB Output is correct
40 Correct 1780 ms 168404 KB Output is correct
41 Correct 1698 ms 169564 KB Output is correct
42 Correct 1670 ms 156816 KB Output is correct
43 Correct 1150 ms 119200 KB Output is correct
44 Correct 1145 ms 117788 KB Output is correct
45 Correct 1098 ms 117000 KB Output is correct
46 Correct 1231 ms 127952 KB Output is correct
47 Correct 1369 ms 143256 KB Output is correct
48 Correct 1543 ms 152372 KB Output is correct
49 Correct 1454 ms 144500 KB Output is correct
50 Correct 1839 ms 166352 KB Output is correct
51 Correct 983 ms 140732 KB Output is correct
52 Correct 1002 ms 147552 KB Output is correct
53 Correct 1033 ms 141380 KB Output is correct