oj.uz

Submission #633345

# Submission time Handle Problem Language Result Execution time Memory
633345 2022-08-22T07:03:09 Z codr0 Dabbeh (INOI20_dabbeh) C++14
0 / 100
 831 ms 56448 KB 
// Code by Parsa Eslami

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define bit(i,j) ((j>>i)&1)
#define F first
#define S second
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1
#define err(x) cerr<<#x<<"="<<x<<'\n'
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;
const int md=1000696969;
const int base=31;
const int N=3e5+4;
const int lg=20;
int PW[N],inv[N];
int hsh[N];
int nxt[lg][N];
int big[lg][N];

	inline int mkey(int a,int b){ int rt=a+b; if(rt>=md) rt-=md; return rt;}

	int pw(int a,int b){
		int rt=1;
		while(b){
			if(b&1) rt=1LL*rt*a%md;
			a=1LL*a*a%md;
			b/=2;
		}
		return rt;
	}

	int h(int l,int r){
		int rt=mkey(hsh[r],md-hsh[l-1]);
		rt=1LL*rt*inv[l-1]%md;
		return rt;
	}

	int32_t main(){
	iostream::sync_with_stdio(0); cin.tie(0);

	PW[0]=1; FOR(i,1,N-1) PW[i]=1LL*PW[i-1]*base%md;
	inv[N-1]=pw(PW[N-1],md-2); FORR(i,N-2,0) inv[i]=1LL*inv[i+1]*base%md;
	int n,m; cin>>n>>m;
	vector<pii> vc;
	FOR(i,1,n){
		string x; cin>>x;
		int HSH=0;
		FOR(j,0,SZ(x)-1){
			HSH=mkey(HSH,1LL*(x[j]-'a'+1)*PW[j]%md);
			vc.pb({HSH,j+1});
		}
	}
	sort(all(vc));
	string s; cin>>s;
	s='#'+s;
	FOR(i,1,SZ(s)-1){
		hsh[i]=mkey(hsh[i-1],1LL*PW[i-1]*(s[i]-'a'+1)%md);
	}
	vector<pii> st;
	FORR(i,SZ(s)-2,0){
		int l=i,r=SZ(s);
		while(r-l>1){
			dmid;
			int HSH=h(i+1,mid);
			pii ty={HSH,mid-i};
			auto it=lower_bound(all(vc),ty);
			if(*it==ty) l=mid;
			else r=mid;
		}
		int L=-1,R=SZ(st);
		while(R-L>1){
			int mid=(R+L)/2;
			if(st[mid].S<=l) R=mid;
			else L=mid;
		}
		if(R==SZ(st)||st[R].F<=l) nxt[0][i]=l;
		else nxt[0][i]=st[R].S;
		while(!st.empty()&&st.back().F<=l) st.pop_back();
		st.pb({l,i});
		big[0][i]=l;
	}
	nxt[0][SZ(s)-1]=SZ(s)-1;
	FOR(j,1,lg-1) FOR(i,0,SZ(s)-1) nxt[j][i]=nxt[j-1][nxt[j-1][i]];
	FOR(j,1,lg-1) FOR(i,0,SZ(s)-1) big[j][i]=big[j-1][nxt[j-1][i]];
//	FOR(i,0,SZ(s)-1) cout<<nxt[0][i]<<" ";
//	cout<<'\n';
	while(m--){
		int l,r; cin>>l>>r;
		int ans=0;
		FORR(j,lg-1,0) if(nxt[j][l]<r&&big[j][l]<r){
	//		cout<<l<<" "<<j<<" "<<nxt[j][l]<<'\n';
			l=nxt[j][l];
			ans+=(1<<j);
		}
		ans++;
		if(ans>SZ(s)) ans=-1;
		cout<<ans<<'\n';
	}

	return 0;
	}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2900 KB Output is correct
2 Correct 105 ms 6920 KB Output is correct
3 Correct 105 ms 8552 KB Output is correct
4 Correct 137 ms 9632 KB Output is correct
5 Correct 120 ms 9232 KB Output is correct
6 Correct 130 ms 10128 KB Output is correct
7 Correct 132 ms 10492 KB Output is correct
8 Correct 166 ms 10336 KB Output is correct
9 Correct 117 ms 9888 KB Output is correct
10 Correct 86 ms 7108 KB Output is correct
11 Runtime error 17 ms 12036 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 831 ms 56448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2900 KB Output is correct
2 Correct 105 ms 6920 KB Output is correct
3 Correct 105 ms 8552 KB Output is correct
4 Correct 137 ms 9632 KB Output is correct
5 Correct 120 ms 9232 KB Output is correct
6 Correct 130 ms 10128 KB Output is correct
7 Correct 132 ms 10492 KB Output is correct
8 Correct 166 ms 10336 KB Output is correct
9 Correct 117 ms 9888 KB Output is correct
10 Correct 86 ms 7108 KB Output is correct
11 Runtime error 17 ms 12036 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -