Submission #634232

#	Time	Username	Problem	Language	Result	Execution time	Memory
634232		S2speed	Dabbeh (INOI20_dabbeh)	C++17	0 / 100	2087 ms	104872 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")

#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;

const ll maxn = 9e5 + 17 , md = 2000000357 , P = 131 , inf = 2e16;

struct segtree {

	ll sz = 1;
	vector<pll> val;

	void init(ll n){
		while(sz < n) sz <<= 1;
		val.assign(sz << 1 , {-1 , -1});
		return;
	}

	void build(vector<pll> &a , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			if(lx < sze(a)){
				val[x] = a[lx];
			}
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		build(a , ln , lx , m); build(a , rn , m , rx);
		val[x] = max(val[ln] , val[rn]);
		return;
	}

	void build(vector<pll> &a){
		build(a , 0 , 0 , sz);
		return;
	}

	pll cal(ll l , ll r , ll x , ll lx , ll rx){
		if(rx <= l || lx >= r) return {-1 , -1};
		if(rx <= r && lx >= l) return val[x];
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		pll a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
		return max(a , b);
	}

	pll cal(ll l , ll r){
		return cal(l , r , 0 , 0 , sz);
	}

};

segtree st;
ll k , q , n , m;
ll tv[maxn];
string t[maxn] , s;
ll r[maxn] , rnk[maxn] , sf[maxn] , hs[maxn] , l[maxn];
ll mx[maxn] , f[maxn] , jad[maxn][20];
vector<ll> cnt[maxn] , v;
vector<pll> a;

ll get_hs(ll l , ll r){
	if(r > n) return -inf - l;
	ll res = hs[r - 1];
	if(l){
		res -= hs[l - 1] * tv[r - l];
		res %= md; res += (res < 0) * md;
	}
	return res;
}

ll lcp(ll i , ll j){
	ll l = 0 , r = n;
	while(l < r - 1){
		ll m = (r + l) >> 1;
		if(get_hs(i , i + m) == get_hs(j , j + m)){
			l = m;
		} else {
			r = m;
		}
	}
	return l;
}

int main(){
	ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);

	tv[0] = 1;
	for(ll i = 1 ; i < maxn ; i++){
		tv[i] = tv[i - 1] * P % md;
	}
	cin>>k>>q;
	for(ll i = 0 ; i < k ; i++){
		cin>>t[i];
	}
	cin>>s; m = sze(s);
	s += '{';
	for(ll i = 0 ; i < k ; i++){
		s += t[i]; s += '{';
	}
	n = sze(s);
	hs[0] = s[0];
	for(ll i = 1 ; i < n ; i++){
		hs[i] = (hs[i - 1] * P + s[i]) % md;
	}
	ll lm = max(n , 131ll);
	for(ll i = 0 ; i < n ; i++){
		r[i] = s[i];
	}
	for(ll z = 1 ; z < n ; z <<= 1){
		for(ll i = 0 ; i + z < n ; i++){
			rnk[i] = r[i + z];
		}
		for(ll i = n - z ; i < n ; i++){
			rnk[i] = 0;
		}
		for(ll i = 0 ; i <= lm ; i++) cnt[i].clear();
		v.clear();
		for(ll i = 0 ; i < n ; i++){
			cnt[rnk[i]].push_back(i);
		}
		for(ll i = 0 ; i <= lm ; i++){
			for(auto j : cnt[i]) v.push_back(j);
		}
		for(ll i = 0 ; i <= lm ; i++) cnt[i].clear();
		for(auto i : v){
			cnt[r[i]].push_back(i);
		}
		ll o = 0;
		for(ll i = 0 ; i <= lm ; i++){
			if(cnt[i].empty()) continue;
			r[cnt[i][0]] = ++o;
			ll cs = sze(cnt[i]);
			for(ll e = 1 ; e < cs ; e++){
				ll j = cnt[i][e] , pr = cnt[i][e - 1];
				if(rnk[j] == rnk[pr]){
					r[j] = o;
				} else {
					r[j] = ++o;
				}
			}
		}
	}
	for(ll i = 0 ; i < n ; i++){
		sf[r[i] - 1] = i;
	}
//	for(ll i = 0 ; i < n ; i++){
//		cout<<sf[i]<<' ';
//	}
//	cout<<'\n';
	for(ll i = 0 ; i < n - 1 ; i++){
		l[i] = lcp(sf[i] , sf[i + 1]);
//		cout<<l[i]<<' ';
	}
//	cout<<'\n';
	ll t = -1;
	for(ll i = 0 ; i < n ; i++){
		if(sf[i] < m){
			mx[sf[i]] = t;
		} else if(s[sf[i] - 1] == '{'){
			t = n - sf[i];
		}
		t = min(t , l[i]);
	}
	t = -1;
	for(ll i = n - 1 ; ~i ; i--){
		t = min(t , l[i]);
		if(sf[i] < m){
			mx[sf[i]] = max(mx[sf[i]] , t);
		} else if(s[sf[i] - 1] == '{'){
			t = n - sf[i];
		}
	}
	for(ll i = 0 ; i < m ; i++){
		f[i] = min(m , i + mx[i]);
//		cout<<f[i]<<' ';
		a.push_back({f[i] , i});
	}
//	cout<<'\n';
	st.init(m);
	st.build(a);
	for(ll i = m - 1 ; ~i ; i--){
		pll p = st.cal(i + 1 , f[i] + 1);
		if(p.first <= f[i]){
			for(ll j = 0 ; j < 20 ; j++){
				jad[i][j] = i;
			}
			continue;
		}
		jad[i][0] = p.second;
		for(ll j = 1 ; j < 20 ; j++){
			jad[i][j] = jad[jad[i][j - 1]][j - 1];
		}
	}
	for(ll i = 0 ; i < m ; i++){
//		cout<<jad[i][0]<<' ';
	}
//	cout<<'\n';
	for(ll e = 0 ; e < q ; e++){
		ll l , r;
		cin>>l>>r;
		if(f[jad[l][19]] < r){
			cout<<"-1\n";
			continue;
		}
		if(f[l] >= r){
			cout<<"1\n";
			continue;
		}
		ll v = l , res = 2;
		for(ll j = 19 ; ~j ; j--){
			ll u = jad[v][j];
			if(f[u] >= r) continue;
			v = u; res += (1 << j);
		}
		cout<<res<<'\n';
	}
	return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 50