oj.uz

답안 #1002111

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1002111 2024-06-19T10:02:05 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 205304 KB 
#include <bits/stdc++.h>

using namespace std;

#define int 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 binpow(a, b - 1, m) % m * a % m;
    return binpow(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 {(pre[r].first - pre[l - 1].first + 2 * MOD1) % MOD1 * invP[l - 1].first % MOD1,
            (pre[r].second - pre[l - 1].second + 2 * 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 = P[i - 1].first * B % MOD1;
        P[i].second = P[i - 1].second * B % MOD2;
        invP[i].first = invP[i - 1].first * inv(B, MOD1) % MOD1;
        invP[i].second = 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 + (t[i][j] - 'a' + 1) * P[j].first % MOD1) % MOD1;
            H.second = (H.second + (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 + (s[i - 1] - 'a' + 1) * P[i - 1].first % MOD1) % MOD1;
        pre[i].second = (pre[i - 1].second + (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;
        }
        int ans = 0;
        for(int i = LOGMAX - 1; i >= 0; i--){
            if(nxt[par[i][l]] <= r){
                ans += (1 << 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:71: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]
   71 |         for(int j = 0; j < t[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 378 ms 63056 KB Output is correct
2 Correct 575 ms 89988 KB Output is correct
3 Correct 532 ms 83828 KB Output is correct
4 Correct 568 ms 90068 KB Output is correct
5 Correct 597 ms 87892 KB Output is correct
6 Correct 580 ms 94032 KB Output is correct
7 Correct 617 ms 97200 KB Output is correct
8 Correct 595 ms 95856 KB Output is correct
9 Correct 547 ms 92752 KB Output is correct
10 Correct 415 ms 72528 KB Output is correct
11 Correct 572 ms 94036 KB Output is correct
12 Correct 449 ms 79204 KB Output is correct
13 Correct 495 ms 87528 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2083 ms 205304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 378 ms 63056 KB Output is correct
2 Correct 575 ms 89988 KB Output is correct
3 Correct 532 ms 83828 KB Output is correct
4 Correct 568 ms 90068 KB Output is correct
5 Correct 597 ms 87892 KB Output is correct
6 Correct 580 ms 94032 KB Output is correct
7 Correct 617 ms 97200 KB Output is correct
8 Correct 595 ms 95856 KB Output is correct
9 Correct 547 ms 92752 KB Output is correct
10 Correct 415 ms 72528 KB Output is correct
11 Correct 572 ms 94036 KB Output is correct
12 Correct 449 ms 79204 KB Output is correct
13 Correct 495 ms 87528 KB Output is correct
14 Execution timed out 2083 ms 205304 KB Time limit exceeded
15 Halted 0 ms 0 KB -