oj.uz

Submission #1002130

# Submission time Handle Problem Language Result Execution time Memory
1002130 2024-06-19T10:17:05 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 181564 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 int MAX = 5e5 + 5, B = 61, MOD1 = 1e9 + 7, MOD2 = 1e9 + 9, 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));
    }
};
int binpow(int a, int b, int m){
    if(b == 0) return 1;
    if(b & 1) return 1ll * binpow(a, b - 1, m) % m * a % m;
    return 1ll * binpow(1ll * a * a % m, b / 2, m) % m;
}
int inv(int a, int m){
    return binpow(a, m - 2, m);
}
int n, q;
string s;
string t[MAX];

map<pii, int> mp;
pii pre[MAX];
pii P[(int)5e5 + 5];
pii invP[(int)5e5 + 5];
ST st;
int par[LOGMAX][MAX];
int nxt[MAX];

pii calc(int l, int r){
    return {1ll * (pre[r].first - pre[l - 1].first + MOD1) % MOD1 * invP[l - 1].first % MOD1,
            1ll * (pre[r].second - pre[l - 1].second + MOD2) % MOD2 * invP[l - 1].second % MOD2};
}


void solve(){
    P[0]= {1, 1};
    invP[0] = {1, 1};
    for(int i = 1; i <= 5e5; i++){
        P[i].first = 1ll * P[i - 1].first * B % MOD1;
        P[i].second = 1ll * P[i - 1].second * B % MOD2;
        invP[i].first = 1ll * invP[i - 1].first * inv(B, MOD1) % MOD1;
        invP[i].second = 1ll * invP[i - 1].second * inv(B, MOD2) % MOD2;
    }
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> t[i];
        pii H = {0, 0};
        for(int j = 0; j < t[i].size(); j++){
            H.first = (1ll * H.first + 1ll * (t[i][j] - 'a' + 1) * P[j].first % MOD1) % MOD1;
            H.second = (1ll * H.second + 1ll * (t[i][j] - 'a' + 1) * P[j].second % MOD2) % MOD2;
            mp[H] = 1;
        }
    }
    cin >> s;
    n = s.size();
    for(int i = 1; i <= n; i++){
        pre[i].first = (1ll * pre[i - 1].first + 1ll * (s[i - 1] - 'a' + 1) * P[i - 1].first % MOD1) % MOD1;
        pre[i].second = (1ll * pre[i - 1].second + 1ll * (s[i - 1] - 'a' + 1) * P[i - 1].second % MOD2) % MOD2;
    }
    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[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[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 352 ms 39764 KB Output is correct
2 Correct 565 ms 66472 KB Output is correct
3 Correct 532 ms 60244 KB Output is correct
4 Correct 583 ms 66644 KB Output is correct
5 Correct 570 ms 64416 KB Output is correct
6 Correct 599 ms 70508 KB Output is correct
7 Correct 602 ms 73636 KB Output is correct
8 Correct 633 ms 72224 KB Output is correct
9 Correct 578 ms 69152 KB Output is correct
10 Correct 461 ms 48976 KB Output is correct
11 Correct 565 ms 70632 KB Output is correct
12 Correct 430 ms 55696 KB Output is correct
13 Correct 499 ms 63960 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 181564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 39764 KB Output is correct
2 Correct 565 ms 66472 KB Output is correct
3 Correct 532 ms 60244 KB Output is correct
4 Correct 583 ms 66644 KB Output is correct
5 Correct 570 ms 64416 KB Output is correct
6 Correct 599 ms 70508 KB Output is correct
7 Correct 602 ms 73636 KB Output is correct
8 Correct 633 ms 72224 KB Output is correct
9 Correct 578 ms 69152 KB Output is correct
10 Correct 461 ms 48976 KB Output is correct
11 Correct 565 ms 70632 KB Output is correct
12 Correct 430 ms 55696 KB Output is correct
13 Correct 499 ms 63960 KB Output is correct
14 Execution timed out 2068 ms 181564 KB Time limit exceeded
15 Halted 0 ms 0 KB -