oj.uz

Submission #1002128

# Submission time Handle Problem Language Result Execution time Memory
1002128 2024-06-19T10:13:31 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 197976 KB 
#include <bits/stdc++.h>

using namespace std;

// #define int long long
#define ll long long
#define pii pair<ll, ll>
#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 + 2ll * MOD1) % MOD1 * invP[l - 1].first % MOD1,
            1ll * (pre[r].second - pre[l - 1].second + 2ll * 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 = (H.first + 1ll * (t[i][j] - 'a' + 1) * P[j].first % MOD1) % MOD1;
            H.second = (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 = (pre[i - 1].first + 1ll * (s[i - 1] - 'a' + 1) * P[i - 1].first % MOD1) % MOD1;
        pre[i].second = (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 345 ms 63172 KB Output is correct
2 Correct 552 ms 90044 KB Output is correct
3 Correct 509 ms 83796 KB Output is correct
4 Correct 560 ms 89904 KB Output is correct
5 Correct 558 ms 87920 KB Output is correct
6 Correct 592 ms 94032 KB Output is correct
7 Correct 632 ms 97336 KB Output is correct
8 Correct 588 ms 95588 KB Output is correct
9 Correct 603 ms 92724 KB Output is correct
10 Correct 473 ms 72528 KB Output is correct
11 Correct 577 ms 94000 KB Output is correct
12 Correct 460 ms 79132 KB Output is correct
13 Correct 505 ms 87268 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 63172 KB Output is correct
2 Correct 552 ms 90044 KB Output is correct
3 Correct 509 ms 83796 KB Output is correct
4 Correct 560 ms 89904 KB Output is correct
5 Correct 558 ms 87920 KB Output is correct
6 Correct 592 ms 94032 KB Output is correct
7 Correct 632 ms 97336 KB Output is correct
8 Correct 588 ms 95588 KB Output is correct
9 Correct 603 ms 92724 KB Output is correct
10 Correct 473 ms 72528 KB Output is correct
11 Correct 577 ms 94000 KB Output is correct
12 Correct 460 ms 79132 KB Output is correct
13 Correct 505 ms 87268 KB Output is correct
14 Execution timed out 2055 ms 197976 KB Time limit exceeded
15 Halted 0 ms 0 KB -