oj.uz

Submission #634428

# Submission time Handle Problem Language Result Execution time Memory
634428 2022-08-24T11:39:20 Z MohammadAghil Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 61604 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define pb puhs_back
#define ff first
#define ss second

//void dbgg(){
//    cerr << endl;
//}
//template<typename Head, typename... Tail> dbgg(Head h, Tail... t){
//    cerr<< " " << h << ",";
//    dbg(t...);
//}
//#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">:", dbgg(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void IOS(){
    cin.tie(0) -> sync_with_stdio(0);
//    #ifndef ONLINE_JUDGE
//        freopen("inp.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
//    #endif
}

const ll mod = 1e9 + 7, mod2 = 1e9 + 9, maxn = 3e5 + 5, lg = 19, inf = ll(1e9) + 5, p = 9973;

struct C{
    int operator()(pair<int, int> x) const {
        return x.ff^x.ss;
    }
};

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

gp_hash_table<pair<int, int>, bool, C> is;

void add(string s){
    pp hsh = {0, 0};
    for(char c: s){
        hsh.ff = (hsh.ff*p + c - 'a' + 1)%mod;
        hsh.ss = (hsh.ss*p + c - 'a' + 1)%mod2;
        is[hsh] = true;
    }
}

ll pw1[maxn], pw2[maxn];
pp hsh[maxn];

void build_hash(string s){
    rep(i,0,sz(s)){
        hsh[i].ff = ((i?hsh[i-1].ff:0)*p + s[i] - 'a' + 1)%mod;
        hsh[i].ss = ((i?hsh[i-1].ss:0)*p + s[i] - 'a' + 1)%mod2;
    }
    pw1[0] = pw2[0] = 1;
    rep(i,1,sz(s) + 1){
        pw1[i] = pw1[i-1]*p%mod;
        pw2[i] = pw2[i-1]*p%mod2;
    }
}

pair<int, int> get_hsh(int l, int r){
    return {
        (hsh[r].ff - (l?hsh[l-1].ff*pw1[r-l+1]%mod:0) + mod)%mod,
        (hsh[r].ss - (l?hsh[l-1].ss*pw2[r-l+1]%mod2:0) + mod2)%mod2
    };
}

int nxt[maxn][lg], nxt_id[maxn][lg];
pair<int, int> rmq[maxn][lg];
int lgg[maxn], m;

void build_rmq(int x){
    m++;
    rep(i,0,m) rmq[i][0] = {nxt[i][x], i};
    rep(i,2,m + 1) lgg[i] = lgg[i>>1] + 1;
    rep(j,1,lg){
        rep(i,0,m - (1<<j) + 1){
            rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
        }
    }
    m--;
}

pp get_rmq(int l, int r){
    int k = lgg[r - l + 1];
    return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
}

int main(){ IOS();
    int n, q; cin >> n >> q;
    rep(i,0,n){
        string t; cin >> t;
        add(t);
    }
    string s; cin >> s;
    build_hash(s);

    m = sz(s);
    rep(j,0,lg) nxt[m][j] = nxt_id[m][j] = m;
    rep(i,0,m){
        int lx = i-1, rx = m;
        while(lx + 1 < rx){
            int mid = (lx + rx)>>1;
            if(is[get_hsh(i, mid)]) lx = mid;
            else rx = mid;
        }
        nxt[i][0] = rx;
    }

    build_rmq(0);

    rep(i,0,m){
        nxt_id[i][0] = get_rmq(i, nxt[i][0]).ss;
    }

    rep(j,1,lg){
        rep(i,0,m){
            nxt[i][j] = nxt[nxt_id[i][j-1]][j-1], nxt_id[i][j] = nxt_id[nxt_id[i][j-1]][j-1];
        }
    }

    while(q--){
        int l, r; cin >> l >> r; r--;
        if(nxt[l][lg-1] <= r) cout << -1 << '\n';
        else{
            int ans = 0;
            per(i,lg-1,0){
                int nx = nxt[l][i];
                if(nx <= r){
                    ans |= 1<<i;
                    l = nxt_id[l][i];
                }
            }
            cout << ans + 1 << '\n';
        }
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 155 ms 25824 KB Output is correct
3 Correct 148 ms 25920 KB Output is correct
4 Correct 279 ms 25988 KB Output is correct
5 Correct 136 ms 26096 KB Output is correct
6 Correct 193 ms 26008 KB Output is correct
7 Correct 121 ms 26176 KB Output is correct
8 Correct 122 ms 25928 KB Output is correct
9 Correct 117 ms 25964 KB Output is correct
10 Correct 80 ms 7440 KB Output is correct
11 Correct 106 ms 26016 KB Output is correct
12 Correct 81 ms 13340 KB Output is correct
13 Correct 99 ms 25860 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 155 ms 25824 KB Output is correct
3 Correct 148 ms 25920 KB Output is correct
4 Correct 279 ms 25988 KB Output is correct
5 Correct 136 ms 26096 KB Output is correct
6 Correct 193 ms 26008 KB Output is correct
7 Correct 121 ms 26176 KB Output is correct
8 Correct 122 ms 25928 KB Output is correct
9 Correct 117 ms 25964 KB Output is correct
10 Correct 80 ms 7440 KB Output is correct
11 Correct 106 ms 26016 KB Output is correct
12 Correct 81 ms 13340 KB Output is correct
13 Correct 99 ms 25860 KB Output is correct
14 Execution timed out 2066 ms 61604 KB Time limit exceeded
15 Halted 0 ms 0 KB -