oj.uz

Submission #633350

# Submission time Handle Problem Language Result Execution time Memory
633350 2022-08-22T07:26:42 Z codr0 Dabbeh (INOI20_dabbeh) C++14
0 / 100
 813 ms 56432 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)-1,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!=vc.end()&&(*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)) nxt[0][i]=l;
		else nxt[0][i]=st[R].S;
	/*	if(l==9){
			for(pii x0:st) cout<<x0.F<<","<<x0.S<<' ';
			cout<<'\n';
			cout<<R<<'\n';
		}*/
		while(!st.empty()&&st.back().F<=l) st.pop_back();
		st.pb({l,i});	
		big[0][i]=l;
	}	
	nxt[0][SZ(s)-1]=big[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<<big[0][i]<<" ";
//	cout<<'\n';
	while(m--){
		int l,r; cin>>l>>r;
		int ans=0;
		FORR(j,lg-1,0) if(big[j][l]<r){
		//	cout<<l<<" "<<j<<'\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 4 ms 2900 KB Output is correct
2 Correct 110 ms 6864 KB Output is correct
3 Correct 108 ms 6820 KB Output is correct
4 Correct 117 ms 7024 KB Output is correct
5 Correct 115 ms 6864 KB Output is correct
6 Correct 132 ms 7460 KB Output is correct
7 Correct 131 ms 7792 KB Output is correct
8 Correct 126 ms 7820 KB Output is correct
9 Correct 118 ms 7248 KB Output is correct
10 Correct 89 ms 4692 KB Output is correct
11 Runtime error 16 ms 11388 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 813 ms 56432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 110 ms 6864 KB Output is correct
3 Correct 108 ms 6820 KB Output is correct
4 Correct 117 ms 7024 KB Output is correct
5 Correct 115 ms 6864 KB Output is correct
6 Correct 132 ms 7460 KB Output is correct
7 Correct 131 ms 7792 KB Output is correct
8 Correct 126 ms 7820 KB Output is correct
9 Correct 118 ms 7248 KB Output is correct
10 Correct 89 ms 4692 KB Output is correct
11 Runtime error 16 ms 11388 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -