oj.uz

답안 #634411

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
634411 2022-08-24T11:06:47 Z MohammadAghil Dabbeh (INOI20_dabbeh) C++17
0 / 100
 2000 ms 107032 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 + 9, mod2 = 1e9 + 9, maxn = 5e5 + 5, lg = 19, inf = ll(1e9) + 5, p = 9973;

map<int, bool> is;

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

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

void build_hash(string s){
    rep(i,0,sz(s)){
        hsh[i] = ((i?hsh[i-1]:0)*p + s[i] - 'a' + 1)%mod;
//        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;
    }
}

int get_hsh(int l, int r){
    return (hsh[r] - (l?hsh[l-1]*pw1[r-l+1]%mod:0) + mod)%mod;
//    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
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 326 ms 18900 KB Output is correct
3 Incorrect 203 ms 14028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 326 ms 18900 KB Output is correct
3 Incorrect 203 ms 14028 KB Output isn't correct
4 Halted 0 ms 0 KB -