oj.uz

Submission #633346

# Submission time Handle Problem Language Result Execution time Memory
633346 2022-08-22T07:05:16 Z codr0 Dabbeh (INOI20_dabbeh) C++14
0 / 100
 820 ms 56520 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!=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)||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 4 ms 2900 KB Output is correct
2 Correct 108 ms 6852 KB Output is correct
3 Correct 105 ms 6864 KB Output is correct
4 Correct 119 ms 7004 KB Output is correct
5 Correct 113 ms 6836 KB Output is correct
6 Correct 121 ms 7464 KB Output is correct
7 Correct 130 ms 7808 KB Output is correct
8 Correct 125 ms 7752 KB Output is correct
9 Correct 119 ms 7208 KB Output is correct
10 Correct 86 ms 4716 KB Output is correct
11 Runtime error 16 ms 11432 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 820 ms 56520 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 108 ms 6852 KB Output is correct
3 Correct 105 ms 6864 KB Output is correct
4 Correct 119 ms 7004 KB Output is correct
5 Correct 113 ms 6836 KB Output is correct
6 Correct 121 ms 7464 KB Output is correct
7 Correct 130 ms 7808 KB Output is correct
8 Correct 125 ms 7752 KB Output is correct
9 Correct 119 ms 7208 KB Output is correct
10 Correct 86 ms 4716 KB Output is correct
11 Runtime error 16 ms 11432 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -