oj.uz

답안 #634403

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

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

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 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 -