Submission #469764

#	Time	Username	Problem	Language	Result	Execution time	Memory
469764		alirezasamimi100	Dabbeh (INOI20_dabbeh)	C++17	25 / 100	2108 ms	518468 KiB

Main

#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 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 50