oj.uz

Submission #1002299

# Submission time Handle Problem Language Result Execution time Memory
1002299 2024-06-19T12:13:37 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 47604 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];

vector<pii> 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.push_back({H.first, H.second});
        }
    }
    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(find(mp.begin(), mp.end(), calc(i, i)) == mp.end()){
            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(find(mp.begin(), mp.end(), calc(i, mid)) != mp.end()) 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 382 ms 39508 KB Output is correct
2 Correct 474 ms 46032 KB Output is correct
3 Correct 567 ms 45516 KB Output is correct
4 Correct 707 ms 46588 KB Output is correct
5 Correct 750 ms 46176 KB Output is correct
6 Correct 781 ms 47312 KB Output is correct
7 Correct 855 ms 47604 KB Output is correct
8 Correct 836 ms 47564 KB Output is correct
9 Correct 746 ms 46988 KB Output is correct
10 Correct 512 ms 43740 KB Output is correct
11 Correct 417 ms 47316 KB Output is correct
12 Correct 420 ms 44624 KB Output is correct
13 Correct 416 ms 45916 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 39508 KB Output is correct
2 Correct 474 ms 46032 KB Output is correct
3 Correct 567 ms 45516 KB Output is correct
4 Correct 707 ms 46588 KB Output is correct
5 Correct 750 ms 46176 KB Output is correct
6 Correct 781 ms 47312 KB Output is correct
7 Correct 855 ms 47604 KB Output is correct
8 Correct 836 ms 47564 KB Output is correct
9 Correct 746 ms 46988 KB Output is correct
10 Correct 512 ms 43740 KB Output is correct
11 Correct 417 ms 47316 KB Output is correct
12 Correct 420 ms 44624 KB Output is correct
13 Correct 416 ms 45916 KB Output is correct
14 Execution timed out 2068 ms 44428 KB Time limit exceeded
15 Halted 0 ms 0 KB -