oj.uz

Submission #634247

# Submission time Handle Problem Language Result Execution time Memory
634247 2022-08-24T07:48:46 Z S2speed Dabbeh (INOI20_dabbeh) C++17
0 / 100
 2000 ms 87516 KB 
#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 = 9e5 + 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] , l[maxn];
int mx[maxn] , f[maxn] , jad[maxn][20];
vector<int> cnt[maxn];
int v[maxn] , x;
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;
	}
	int lm = max(n , 131);
	for(int i = 0 ; i < n ; i++){
		r[i] = s[i];
	}
	for(int z = 1 ; z < n ; z <<= 1){
		for(int i = 0 ; i + z < n ; i++){
			rnk[i] = r[i + z];
		}
		for(int i = n - z ; i < n ; i++){
			rnk[i] = 0;
		}
		for(int i = 0 ; i <= lm ; i++) cnt[i].clear();
		x = 0;
		for(int i = 0 ; i < n ; i++){
			cnt[rnk[i]].push_back(i);
		}
		for(int i = 0 ; i <= lm ; i++){
			for(auto j : cnt[i]) v[x++] = j;
		}
		for(int i = 0 ; i <= lm ; i++) cnt[i].clear();
		for(int j = 0 ; j < x ; j++){
			int i = v[j];
			cnt[r[i]].push_back(i);
		}
		int o = 0;
		for(int i = 0 ; i <= lm ; i++){
			if(cnt[i].empty()) continue;
			r[cnt[i][0]] = ++o;
			int cs = sze(cnt[i]);
			for(int e = 1 ; e < cs ; e++){
				int j = cnt[i][e] , pr = cnt[i][e - 1];
				if(rnk[j] == rnk[pr]){
					r[j] = o;
				} else {
					r[j] = ++o;
				}
			}
		}
	}
	for(int i = 0 ; i < n ; i++){
		sf[r[i] - 1] = i;
	}
//	for(int i = 0 ; i < n ; i++){
//		cout<<sf[i]<<' ';
//	}
//	cout<<'\n';
	for(int i = 0 ; i < n - 1 ; i++){
		l[i] = lcp(sf[i] , sf[i + 1]);
//		cout<<l[i]<<' ';
	}
//	cout<<'\n';
	int t = -1;
	for(int 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(int 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(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;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56668 KB Output is correct
2 Correct 1741 ms 86968 KB Output is correct
3 Correct 1202 ms 78892 KB Output is correct
4 Correct 1723 ms 87280 KB Output is correct
5 Correct 1530 ms 82640 KB Output is correct
6 Execution timed out 2069 ms 87280 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 87516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56668 KB Output is correct
2 Correct 1741 ms 86968 KB Output is correct
3 Correct 1202 ms 78892 KB Output is correct
4 Correct 1723 ms 87280 KB Output is correct
5 Correct 1530 ms 82640 KB Output is correct
6 Execution timed out 2069 ms 87280 KB Time limit exceeded
7 Halted 0 ms 0 KB -