Submission #634886

#	Time	Username	Problem	Language	Result	Execution time	Memory
634886		S2speed	Dabbeh (INOI20_dabbeh)	C++17	100 / 100	1877 ms	105400 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;
typedef pair<int , int> pii;

const ll maxn = (1 << 20) + 17 , md = 2000000357 , P = 131 , inf = 2e16;

pii val[maxn];

struct segtree {
 
	int sz = 1;
 
	void init(int n){
		while(sz < n) sz <<= 1;
		fill(val , val + (sz << 1) , make_pair(-1 , -1));
		return;
	}
 
	void build(vector<pii> &a , int x , int lx , int rx){
		if(rx - lx == 1){
			if(lx < sze(a)){
				val[x] = a[lx];
			}
			return;
		}
		int 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<pii> &a){
		build(a , 0 , 0 , sz);
		return;
	}
 
	pii cal(int l , int r , int x , int lx , int rx){
		if(rx <= l || lx >= r) return {-1 , -1};
		if(rx <= r && lx >= l) return val[x];
		int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		pii a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
		return max(a , b);
	}
 
	pii cal(int l , int r){
		return cal(l , r , 0 , 0 , sz);
	}
 
};

segtree st;
int k , q , n , m;
ll tv[maxn] , hs[maxn];
string t[maxn] , s;
int r[maxn] , rnk[maxn] , sf[maxn] , pn[maxn] , cnt[maxn] , x[maxn] , y[maxn] , l[maxn];
int mx[maxn] , f[maxn] , jad[maxn][20];
vector<int> imp;
vector<pii> a;

ll get_hs(int l , int 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;
}

int lcp(int i , int j){
	int l = 0 , r = n;
	while(l < r - 1){
		int 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(int i = 1 ; i < maxn ; i++){
		tv[i] = tv[i - 1] * P % md;
	}
	cin>>k>>q;
	for(int i = 0 ; i < k ; i++){
		cin>>t[i];
	}
	cin>>s; m = sze(s);
	s += '$';
	for(int i = 0 ; i < k ; i++){
		s += t[i]; s += '$';
	}
	n = sze(s);
	hs[0] = s[0];
	for(int i = 1 ; i < n ; i++){
		hs[i] = (hs[i - 1] * P + s[i]) % md;
	}
	for(int i = 0 ; i < n ; i++){
		cnt[s[i]]++;
	}
	int cur = 0 , o = 0;
	for(int i = 0 ; i < 131 ; i++){
		x[i] = cur;
		cur += cnt[i];
		if(cnt[i] > 0){
			y[i] = o++;
		}
	}
	for(int i = 0 ; i < n ; i++){
		sf[x[s[i]]++] = i;
		r[i] = y[s[i]];
	}
	for(int z = 1 ; z < n ; z <<= 1){
		for(int i = 0 ; i < n ; i++){
			pn[i] = (sf[i] - z < 0 ? sf[i] - z + n : sf[i] - z);
		}
		memset(cnt , 0 , 4 * o);
		for(int i = 0 ; i < n ; i++){
			cnt[r[sf[i]]]++;
		}
		for(int i = 1 ; i < o ; i++){
			cnt[i] += cnt[i - 1];
		}
		for(int i = n - 1 ; ~i ; i--){
			sf[--cnt[r[pn[i]]]] = pn[i];
		}
		rnk[sf[0]] = 0;
		o = 0;
		for(int i = 1 ; i < n ; i++){
			pii a = {r[sf[i]] , (sf[i] + z >= n ? r[sf[i] + z - n] : r[sf[i] + z])};
			pii b = {r[sf[i - 1]] , (sf[i - 1] + z >= n ? r[sf[i - 1] + z - n] : r[sf[i - 1] + z])};
			o += (a != b);
			rnk[sf[i]] = o;
		}
		o++;
		memcpy(r , rnk , 4 * n);
	}
//	for(int i = 0 ; i < n ; i++){
//		cout<<sf[i]<<' ';
//	}
//	cout<<'\n';
	for(int i = 0 ; i < n ; i++){
		if(sf[i] < m){
			imp.push_back(i);
		} else if(s[sf[i] - 1] == '$'){
			imp.push_back(i);
		}
	}
//	for(int i = 0 ; i < n ; i++){
//		cout<<sf[i]<<' ';
//	}
//	cout<<'\n';
	int sz = sze(imp);
	for(int i = 0 ; i < sz - 1 ; i++){
		l[i] = lcp(sf[imp[i]] , sf[imp[i + 1]]);
//		cout<<l[i]<<' ';
	}
//	cout<<'\n';
	int t = -1;
	for(int j = 0 ; j < sz ; j++){
		int i = imp[j];
		if(sf[i] < m){
			mx[sf[i]] = t;
		} else {
			t = n - sf[i];
		}
		t = min(t , l[j]);
	}
	t = -1;
	for(int j = sz - 1 ; ~j ; j--){
		int i = imp[j];
		t = min(t , l[j]);
		if(sf[i] < m){
			mx[sf[i]] = max(mx[sf[i]] , t);
		} else {
			t = n - sf[i];
		}
	}
	for(int 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(int i = m - 1 ; ~i ; i--){
		pii p = st.cal(i + 1 , f[i] + 1);
		if(p.first <= f[i]){
			for(int j = 0 ; j < 20 ; j++){
				jad[i][j] = i;
			}
			continue;
		}
		jad[i][0] = p.second;
		for(int j = 1 ; j < 20 ; j++){
			jad[i][j] = jad[jad[i][j - 1]][j - 1];
		}
	}
	for(int i = 0 ; i < m ; i++){
//		cout<<jad[i][0]<<' ';
	}
//	cout<<'\n';
	for(int e = 0 ; e < q ; e++){
		int l , r;
		cin>>l>>r;
		if(f[jad[l][19]] < r){
			cout<<"-1\n";
			continue;
		}
		if(f[l] >= r){
			cout<<"1\n";
			continue;
		}
		int v = l , res = 2;
		for(int j = 19 ; ~j ; j--){
			int u = jad[v][j];
			if(f[u] >= r) continue;
			v = u; res += (1 << j);
		}
		cout<<res<<'\n';
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:112:11: warning: array subscript has type 'char' [-Wchar-subscripts]
  112 |   cnt[s[i]]++;
      |           ^
Main.cpp:123:12: warning: array subscript has type 'char' [-Wchar-subscripts]
  123 |   sf[x[s[i]]++] = i;
      |            ^
Main.cpp:124:16: warning: array subscript has type 'char' [-Wchar-subscripts]
  124 |   r[i] = y[s[i]];
      |                ^

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