oj.uz

Submission #469764

# Submission time Handle Problem Language Result Execution time Memory
469764 2021-09-01T17:56:07 Z alirezasamimi100 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 518468 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 4812 KB Output is correct
2 Correct 557 ms 43248 KB Output is correct
3 Correct 394 ms 34460 KB Output is correct
4 Correct 620 ms 45460 KB Output is correct
5 Correct 468 ms 40272 KB Output is correct
6 Correct 690 ms 51564 KB Output is correct
7 Correct 661 ms 53236 KB Output is correct
8 Correct 705 ms 54688 KB Output is correct
9 Correct 584 ms 48224 KB Output is correct
10 Correct 225 ms 19136 KB Output is correct
11 Correct 426 ms 49052 KB Output is correct
12 Correct 253 ms 27640 KB Output is correct
13 Correct 340 ms 39440 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2108 ms 518468 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 4812 KB Output is correct
2 Correct 557 ms 43248 KB Output is correct
3 Correct 394 ms 34460 KB Output is correct
4 Correct 620 ms 45460 KB Output is correct
5 Correct 468 ms 40272 KB Output is correct
6 Correct 690 ms 51564 KB Output is correct
7 Correct 661 ms 53236 KB Output is correct
8 Correct 705 ms 54688 KB Output is correct
9 Correct 584 ms 48224 KB Output is correct
10 Correct 225 ms 19136 KB Output is correct
11 Correct 426 ms 49052 KB Output is correct
12 Correct 253 ms 27640 KB Output is correct
13 Correct 340 ms 39440 KB Output is correct
14 Execution timed out 2108 ms 518468 KB Time limit exceeded
15 Halted 0 ms 0 KB -