oj.uz

답안 #1002726

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1002726 2024-06-19T18:39:00 Z TheSahib Dabbeh (INOI20_dabbeh) C++14
100 / 100
 1377 ms 130648 KB 
// #pragma optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;

#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, LOGMAX = 18;
const ll MOD = (1ll << 61) - 1;

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;
unordered_set<ll> mp[MAX];
 
ll calc(int l, int r){
    return (__int128_t)(pre[r] - pre[l - 1] + MOD) % MOD * invP[l - 1] % MOD;
}
 
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 < MAX; i++) mp[i].reserve(n / i * 3);

    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].insert(H);
        }
    }
    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:74:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int j = 0; j < t[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 872 ms 82740 KB Output is correct
2 Correct 1012 ms 101924 KB Output is correct
3 Correct 848 ms 97456 KB Output is correct
4 Correct 909 ms 103112 KB Output is correct
5 Correct 886 ms 100392 KB Output is correct
6 Correct 1004 ms 105924 KB Output is correct
7 Correct 901 ms 106448 KB Output is correct
8 Correct 904 ms 106576 KB Output is correct
9 Correct 865 ms 104064 KB Output is correct
10 Correct 887 ms 90156 KB Output is correct
11 Correct 794 ms 99568 KB Output is correct
12 Correct 780 ms 92368 KB Output is correct
13 Correct 844 ms 96428 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 938 ms 115796 KB Output is correct
2 Correct 1067 ms 121128 KB Output is correct
3 Correct 975 ms 116288 KB Output is correct
4 Correct 968 ms 112304 KB Output is correct
5 Correct 998 ms 112224 KB Output is correct
6 Correct 1047 ms 121676 KB Output is correct
7 Correct 1062 ms 123912 KB Output is correct
8 Correct 997 ms 119688 KB Output is correct
9 Correct 948 ms 122636 KB Output is correct
10 Correct 1070 ms 125312 KB Output is correct
11 Correct 1034 ms 117116 KB Output is correct
12 Correct 956 ms 115364 KB Output is correct
13 Correct 974 ms 127100 KB Output is correct
14 Correct 984 ms 124308 KB Output is correct
15 Correct 941 ms 111176 KB Output is correct
16 Correct 930 ms 122084 KB Output is correct
17 Correct 960 ms 112184 KB Output is correct
18 Correct 968 ms 112044 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 872 ms 82740 KB Output is correct
2 Correct 1012 ms 101924 KB Output is correct
3 Correct 848 ms 97456 KB Output is correct
4 Correct 909 ms 103112 KB Output is correct
5 Correct 886 ms 100392 KB Output is correct
6 Correct 1004 ms 105924 KB Output is correct
7 Correct 901 ms 106448 KB Output is correct
8 Correct 904 ms 106576 KB Output is correct
9 Correct 865 ms 104064 KB Output is correct
10 Correct 887 ms 90156 KB Output is correct
11 Correct 794 ms 99568 KB Output is correct
12 Correct 780 ms 92368 KB Output is correct
13 Correct 844 ms 96428 KB Output is correct
14 Correct 938 ms 115796 KB Output is correct
15 Correct 1067 ms 121128 KB Output is correct
16 Correct 975 ms 116288 KB Output is correct
17 Correct 968 ms 112304 KB Output is correct
18 Correct 998 ms 112224 KB Output is correct
19 Correct 1047 ms 121676 KB Output is correct
20 Correct 1062 ms 123912 KB Output is correct
21 Correct 997 ms 119688 KB Output is correct
22 Correct 948 ms 122636 KB Output is correct
23 Correct 1070 ms 125312 KB Output is correct
24 Correct 1034 ms 117116 KB Output is correct
25 Correct 956 ms 115364 KB Output is correct
26 Correct 974 ms 127100 KB Output is correct
27 Correct 984 ms 124308 KB Output is correct
28 Correct 941 ms 111176 KB Output is correct
29 Correct 930 ms 122084 KB Output is correct
30 Correct 960 ms 112184 KB Output is correct
31 Correct 968 ms 112044 KB Output is correct
32 Correct 972 ms 104500 KB Output is correct
33 Correct 1083 ms 114436 KB Output is correct
34 Correct 1057 ms 119288 KB Output is correct
35 Correct 1040 ms 116988 KB Output is correct
36 Correct 1082 ms 121412 KB Output is correct
37 Correct 908 ms 105232 KB Output is correct
38 Correct 1377 ms 129552 KB Output is correct
39 Correct 1286 ms 119880 KB Output is correct
40 Correct 1277 ms 130396 KB Output is correct
41 Correct 1306 ms 130648 KB Output is correct
42 Correct 1197 ms 121792 KB Output is correct
43 Correct 1075 ms 104784 KB Output is correct
44 Correct 1008 ms 104204 KB Output is correct
45 Correct 913 ms 103008 KB Output is correct
46 Correct 940 ms 111324 KB Output is correct
47 Correct 1074 ms 112980 KB Output is correct
48 Correct 1176 ms 119100 KB Output is correct
49 Correct 1081 ms 114100 KB Output is correct
50 Correct 1219 ms 128200 KB Output is correct
51 Correct 1030 ms 109636 KB Output is correct
52 Correct 989 ms 113028 KB Output is correct
53 Correct 980 ms 113796 KB Output is correct