oj.uz

Submission #634403

# Submission time Handle Problem Language Result Execution time Memory
634403 2022-08-24T11:02:32 Z MohammadAghil Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 143740 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 = 5e5 + 5, lg = 19, inf = ll(1e9) + 5, p = 9973;

map<pair<int, int>, bool> 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 1 ms 340 KB Output is correct
2 Correct 329 ms 24932 KB Output is correct
3 Correct 263 ms 18252 KB Output is correct
4 Correct 382 ms 24364 KB Output is correct
5 Correct 313 ms 22240 KB Output is correct
6 Correct 381 ms 28180 KB Output is correct
7 Correct 444 ms 31304 KB Output is correct
8 Correct 392 ms 29804 KB Output is correct
9 Correct 414 ms 26908 KB Output is correct
10 Correct 116 ms 7400 KB Output is correct
11 Correct 365 ms 28324 KB Output is correct
12 Correct 164 ms 13896 KB Output is correct
13 Correct 280 ms 21872 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 329 ms 24932 KB Output is correct
3 Correct 263 ms 18252 KB Output is correct
4 Correct 382 ms 24364 KB Output is correct
5 Correct 313 ms 22240 KB Output is correct
6 Correct 381 ms 28180 KB Output is correct
7 Correct 444 ms 31304 KB Output is correct
8 Correct 392 ms 29804 KB Output is correct
9 Correct 414 ms 26908 KB Output is correct
10 Correct 116 ms 7400 KB Output is correct
11 Correct 365 ms 28324 KB Output is correct
12 Correct 164 ms 13896 KB Output is correct
13 Correct 280 ms 21872 KB Output is correct
14 Execution timed out 2097 ms 143740 KB Time limit exceeded
15 Halted 0 ms 0 KB -