oj.uz

Submission #469732

# Submission time Handle Problem Language Result Execution time Memory
469732 2021-09-01T16:44:46 Z alirezasamimi100 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 518884 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")*/
/*#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
using namespace std;
using ll=long long int;
using ld=long double;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=1e6+10,LN=20,M=5e5+10,SQ=350,B=737,inf=1e9+10;
const ll INF=1e18;
const ld ep=1e-7;
const int MH=1000696969,MD=998244353,MOD=1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
int n,t,q,dp[300001][LN][LN],rnk[20][N],P[N],st[N],f,lg[N];
string s[10001],S;
pii pr[N];
vector<pii> vec;
void bldSA() {
    for (int i=1; i<=t; i++) rnk[0][P[i]=i]=S[i-1];
    for (int pw=1; pw<LN; pw++) {
        for (int i=1; i<=t; i++)
            pr[i]={rnk[pw-1][i],i+(1<<(pw-1))>t?0:rnk[pw-1][i+(1<<(pw-1))]};
        sort(P+1, P+t+1, [&](int x, int y){return pr[x]<pr[y]; });
        rnk[pw][P[1]]=1;
        for (int i=2; i<=t; i++){
            rnk[pw][P[i]]=rnk[pw][P[i-1]]+(pr[P[i]]!=pr[P[i-1]]);
        }
    }
}
int LCP(int x, int y){
    int ans=0;
    for(int i=LN; i--;){
        if(rnk[i][x]==rnk[i][y] && max(x,y)<=t){
            x+=(1<<i);
            y+=(1<<i);
            ans|=(1<<i);
        }
    }
    return ans;
}
int get(int c, int l, int r){
    int x=lg[r-l+1];
    return max(dp[l][c][x],dp[r-(1<<x)+1][c][x]);
}
int main(){
    fast_io;
    for(int i=0; i<LN; i++){
        for(int j=(1<<i); j<(1<<(i+1)); j++) lg[j]=i;
    }
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> s[i];
    cin >> S;
    f=S.size();
    for(int i=1; i<=n; i++){
        st[i]=S.size()+2;
        S+=' '+s[i];
    }
    t=S.size();
    bldSA();
    for(int i=1; i<=n; i++){
        vec.emplace_back(rnk[LN-1][st[i]],i);
    }
    sort(vec.begin(),vec.end());
    for(int i=1; i<=f; i++){
        dp[i][0][0]=i;
        int k=rnk[LN-1][i];
        auto it=lower_bound(vec.begin(),vec.end(),mp(k,0));
        if(it!=vec.end()){
            int c=it->S;
            dp[i][0][0]=max(dp[i][0][0],LCP(i,st[c])+i);
        }
        if(it!=vec.begin()){
            it--;
            int c=it->S;
            dp[i][0][0]=max(dp[i][0][0],LCP(i,st[c])+i);
        }
        dp[i][0][0]=min(dp[i][0][0],f+1);
    }
    for(int j=1; j<LN; j++){
        for(int i=1; i<=f; i++){
            if(i+(1<<(j-1))<=f) dp[i][0][j]=max(dp[i][0][j-1],dp[i+(1<<(j-1))][0][j-1]);
            else dp[i][0][j]=dp[i][0][j-1];
        }
    }
    for(int pw=1; pw<LN; pw++){
        for(int i=1; i<=f; i++){
            dp[i][pw][0]=get(pw-1,i,dp[i][pw-1][0]);
        }
        for(int j=1; j<LN; j++){
            for(int i=1; i<=f; i++){
                    if(i+(1<<(j-1))<=f) dp[i][pw][j]=max(dp[i][pw][j-1],dp[i+(1<<(j-1))][pw][j-1]);
                    else dp[i][pw][j]=dp[i][pw][j-1];
            }
        }
    }
    while(q--){
        int l,r,ans=0,x;
        cin >> l >> r;
        l++;
        r++;
        x=l;
        for(int i=LN; i--;){
            int p=get(i,l,x);
            if(p<r){
                ans|=(1<<i);
                x=p;
            }
        }
        if(get(0,l,x)>=r) cout << ans+1 << '\n';
        else cout << -1 << '\n';
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 1070 ms 43896 KB Output is correct
3 Correct 760 ms 34512 KB Output is correct
4 Correct 1156 ms 45760 KB Output is correct
5 Correct 949 ms 40416 KB Output is correct
6 Correct 1326 ms 51804 KB Output is correct
7 Correct 1304 ms 53252 KB Output is correct
8 Correct 1411 ms 54864 KB Output is correct
9 Correct 1180 ms 48224 KB Output is correct
10 Correct 331 ms 19092 KB Output is correct
11 Correct 684 ms 49068 KB Output is correct
12 Correct 359 ms 27656 KB Output is correct
13 Correct 524 ms 39676 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 1070 ms 43896 KB Output is correct
3 Correct 760 ms 34512 KB Output is correct
4 Correct 1156 ms 45760 KB Output is correct
5 Correct 949 ms 40416 KB Output is correct
6 Correct 1326 ms 51804 KB Output is correct
7 Correct 1304 ms 53252 KB Output is correct
8 Correct 1411 ms 54864 KB Output is correct
9 Correct 1180 ms 48224 KB Output is correct
10 Correct 331 ms 19092 KB Output is correct
11 Correct 684 ms 49068 KB Output is correct
12 Correct 359 ms 27656 KB Output is correct
13 Correct 524 ms 39676 KB Output is correct
14 Execution timed out 2103 ms 518884 KB Time limit exceeded
15 Halted 0 ms 0 KB -