oj.uz

Submission #634427

# Submission time Handle Problem Language Result Execution time Memory
634427 2022-08-24T11:38:48 Z MohammadAghil Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 110744 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<ll, ll>, 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 176 ms 50444 KB Output is correct
3 Correct 167 ms 50516 KB Output is correct
4 Correct 298 ms 50720 KB Output is correct
5 Correct 155 ms 50768 KB Output is correct
6 Correct 215 ms 50632 KB Output is correct
7 Correct 149 ms 50764 KB Output is correct
8 Correct 144 ms 50568 KB Output is correct
9 Correct 145 ms 50632 KB Output is correct
10 Correct 85 ms 13612 KB Output is correct
11 Correct 125 ms 50612 KB Output is correct
12 Correct 92 ms 25696 KB Output is correct
13 Correct 119 ms 50444 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 110744 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 176 ms 50444 KB Output is correct
3 Correct 167 ms 50516 KB Output is correct
4 Correct 298 ms 50720 KB Output is correct
5 Correct 155 ms 50768 KB Output is correct
6 Correct 215 ms 50632 KB Output is correct
7 Correct 149 ms 50764 KB Output is correct
8 Correct 144 ms 50568 KB Output is correct
9 Correct 145 ms 50632 KB Output is correct
10 Correct 85 ms 13612 KB Output is correct
11 Correct 125 ms 50612 KB Output is correct
12 Correct 92 ms 25696 KB Output is correct
13 Correct 119 ms 50444 KB Output is correct
14 Execution timed out 2078 ms 110744 KB Time limit exceeded
15 Halted 0 ms 0 KB -