oj.uz

답안 #634882

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
634882 2022-08-25T08:05:31 Z S2speed Dabbeh (INOI20_dabbeh) C++17
25 / 100
 672 ms 128884 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] , pn[maxn] , cnt[maxn] , x[maxn] , y[maxn] , l[maxn];
int mx[maxn] , f[maxn] , jad[maxn][20];
vector<int> imp;
int v[maxn];
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++){
		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

Main.cpp: In function 'int main()':
Main.cpp:114:11: warning: array subscript has type 'char' [-Wchar-subscripts]
  114 |   cnt[s[i]]++;
      |           ^
Main.cpp:125:12: warning: array subscript has type 'char' [-Wchar-subscripts]
  125 |   sf[x[s[i]]++] = i;
      |            ^
Main.cpp:126:16: warning: array subscript has type 'char' [-Wchar-subscripts]
  126 |   r[i] = y[s[i]];
      |                ^
Main.cpp:112:6: warning: unused variable 'lm' [-Wunused-variable]
  112 |  int lm = max(n , 131);
      |      ^~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 35540 KB Output is correct
2 Correct 447 ms 47996 KB Output is correct
3 Correct 311 ms 44884 KB Output is correct
4 Correct 508 ms 48396 KB Output is correct
5 Correct 416 ms 46684 KB Output is correct
6 Correct 602 ms 50416 KB Output is correct
7 Correct 672 ms 50856 KB Output is correct
8 Correct 647 ms 51252 KB Output is correct
9 Correct 518 ms 49100 KB Output is correct
10 Correct 151 ms 39908 KB Output is correct
11 Correct 196 ms 48468 KB Output is correct
12 Correct 124 ms 42140 KB Output is correct
13 Correct 162 ms 45840 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 640 ms 128884 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 35540 KB Output is correct
2 Correct 447 ms 47996 KB Output is correct
3 Correct 311 ms 44884 KB Output is correct
4 Correct 508 ms 48396 KB Output is correct
5 Correct 416 ms 46684 KB Output is correct
6 Correct 602 ms 50416 KB Output is correct
7 Correct 672 ms 50856 KB Output is correct
8 Correct 647 ms 51252 KB Output is correct
9 Correct 518 ms 49100 KB Output is correct
10 Correct 151 ms 39908 KB Output is correct
11 Correct 196 ms 48468 KB Output is correct
12 Correct 124 ms 42140 KB Output is correct
13 Correct 162 ms 45840 KB Output is correct
14 Runtime error 640 ms 128884 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -