oj.uz

Submission #623694

# Submission time Handle Problem Language Result Execution time Memory
623694 2022-08-06T09:56:44 Z Arinoor Dabbeh (INOI20_dabbeh) C++17
100 / 100
 1022 ms 148896 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define all(x)			x.begin(), x.end()
#define bug(x)			cout << #x << " : " << x << '\n'
#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e4 + 10;
const int maxm = 3e5 + 10;
const int maxl = 1e6 + 10;
const int maxlg = 20;
const int inf = 1e9 + 10;
const char C = 'z' + 1;

int n, l, sz, rnk[maxl << 1], suf[maxl], cnt[maxl], tmp[maxl], lcp[maxl], st[maxn];
int mn[maxlg][maxl], val[maxm], dp[maxlg][maxm];
pii mx[maxlg][maxm];
string s, t[maxn];

bool cmp(int i, int j){
	if(tmp[i] != tmp[j])
		return tmp[i] < tmp[j];
	return max(i, j) + l < n ? tmp[i + l] < tmp[j + l] : i > j;
}

void get_suffix(){
	n = s.size();
	int m = max(n, C - 'a' + 1);
	for(int i = 0; i < n; i ++)
		rnk[i] = s[i] - 'a' + 1;
	l = 1;
	for(; ; l <<= 1){
		memset(cnt, 0, sizeof cnt);
		for(int i = 0; i < n; i ++)
			cnt[rnk[i + l]] ++;
		for(int i = 1; i <= m; i ++)
			cnt[i] += cnt[i - 1];
		for(int i = 0; i < n; i ++)
			tmp[--cnt[rnk[i + l]]] = i;
		memset(cnt, 0, sizeof cnt);
		for(int i = 0; i < n; i ++)
			cnt[rnk[i]] ++;
		for(int i = 1; i <= m; i ++)
			cnt[i] += cnt[i - 1];
		for(int i = n - 1; ~i; i --)
			suf[--cnt[rnk[tmp[i]]]] = tmp[i];
		for(int i = 0; i < n; i ++)
			tmp[i] = rnk[i];
		rnk[suf[0]] = 1;
		for(int i = 1; i < n; i ++)
			rnk[suf[i]] = rnk[suf[i - 1]] + cmp(suf[i - 1], suf[i]);
		if(rnk[suf[n - 1]] == n)
			return;
	}
}

void get_lcp(){
	int len = 0;
	for(int i = 0; i < n; i ++){
		if(rnk[i] == n){
			len = 0;
			continue;
		}
		int j = suf[rnk[i]];
		while(max(i, j) + len < n and s[i + len] == s[j + len])
			len ++;
		lcp[rnk[i] - 1] = len;
		len = max(len - 1, 0);
	}
}

int get_mn(int l, int r){
	int lg = 31 - __builtin_clz(r - l);
	return min(mn[lg][l], mn[lg][r - (1 << lg)]);
}

int get_mx(int l, int r){
	r = min(r + 1, sz);
	int lg = 31 - __builtin_clz(r - l);
	return max(mx[lg][l], mx[lg][r - (1 << lg)]).se;
}

int main(){
	ios;
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i ++)
		cin >> t[i];
	cin >> s;
	int l = s.size();
	sz = l;
	for(int i = 0; i < n; i ++){
		s += C;
		st[i] = s.size();
		s += t[i];
	}
	get_suffix();
	get_lcp();
	for(int i = 0; i < (int)s.size() - 1; i ++)
		mn[0][i] = lcp[i];
	for(int i = 1; i < maxlg; i ++)
		for(int j = 0; j + (1 << i) < (int)s.size(); j ++)
			mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
	vector<int> V;
	for(int i = 0; i < n; i ++)
		V.pb(rnk[st[i]] - 1);
	sort(all(V));
	for(int i = 0; i < l; i ++){
		int idx = rnk[i] - 1;
		int ind = upper_bound(all(V), idx) - V.begin();
		val[i] = 0;
		if(ind != (int)V.size())
			val[i] = get_mn(idx, V[ind]);
		ind --;
		if(ind >= 0)
			val[i] = max(val[i], get_mn(V[ind], idx));
		val[i] += i;
	}
	for(int i = 0; i < l; i ++)
		mx[0][i] = mp(val[i], i);
	for(int i = 1; i < maxlg; i ++)
		for(int j = 0; j + (1 << i) <= l; j ++)
			mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
	for(int i = 0; i < l; i ++)
		dp[0][i] = val[i];
	for(int i = 1; i < maxlg; i ++){
		for(int j = 0; j < l; j ++){
			int ind = get_mx(j, dp[i - 1][j]);
			dp[i][j] = dp[i - 1][ind];
		}
	}
	while(m--){
		int l, r;
		cin >> l >> r;
		if(dp[maxlg - 1][l] < r){
			cout << "-1\n";
			continue;
		}
		int ans = 0;
		for(int i = maxlg - 1; ~i; i --){
			if(dp[i][l] < r){
				ans += 1 << i;
				l = get_mx(l, dp[i][l]);
			}
		}
		cout << ans + 1 << '\n';
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4692 KB Output is correct
2 Correct 151 ms 41724 KB Output is correct
3 Correct 154 ms 32032 KB Output is correct
4 Correct 164 ms 42828 KB Output is correct
5 Correct 185 ms 37540 KB Output is correct
6 Correct 219 ms 48856 KB Output is correct
7 Correct 214 ms 50488 KB Output is correct
8 Correct 217 ms 52072 KB Output is correct
9 Correct 196 ms 45500 KB Output is correct
10 Correct 102 ms 16972 KB Output is correct
11 Correct 304 ms 46264 KB Output is correct
12 Correct 168 ms 25056 KB Output is correct
13 Correct 243 ms 36628 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 112324 KB Output is correct
2 Correct 281 ms 124912 KB Output is correct
3 Correct 204 ms 113296 KB Output is correct
4 Correct 175 ms 104940 KB Output is correct
5 Correct 209 ms 106008 KB Output is correct
6 Correct 220 ms 124484 KB Output is correct
7 Correct 298 ms 131212 KB Output is correct
8 Correct 256 ms 120636 KB Output is correct
9 Correct 248 ms 127132 KB Output is correct
10 Correct 315 ms 133488 KB Output is correct
11 Correct 189 ms 114404 KB Output is correct
12 Correct 214 ms 111556 KB Output is correct
13 Correct 306 ms 135600 KB Output is correct
14 Correct 276 ms 130852 KB Output is correct
15 Correct 190 ms 103236 KB Output is correct
16 Correct 462 ms 135036 KB Output is correct
17 Correct 292 ms 107396 KB Output is correct
18 Correct 291 ms 106924 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4692 KB Output is correct
2 Correct 151 ms 41724 KB Output is correct
3 Correct 154 ms 32032 KB Output is correct
4 Correct 164 ms 42828 KB Output is correct
5 Correct 185 ms 37540 KB Output is correct
6 Correct 219 ms 48856 KB Output is correct
7 Correct 214 ms 50488 KB Output is correct
8 Correct 217 ms 52072 KB Output is correct
9 Correct 196 ms 45500 KB Output is correct
10 Correct 102 ms 16972 KB Output is correct
11 Correct 304 ms 46264 KB Output is correct
12 Correct 168 ms 25056 KB Output is correct
13 Correct 243 ms 36628 KB Output is correct
14 Correct 220 ms 112324 KB Output is correct
15 Correct 281 ms 124912 KB Output is correct
16 Correct 204 ms 113296 KB Output is correct
17 Correct 175 ms 104940 KB Output is correct
18 Correct 209 ms 106008 KB Output is correct
19 Correct 220 ms 124484 KB Output is correct
20 Correct 298 ms 131212 KB Output is correct
21 Correct 256 ms 120636 KB Output is correct
22 Correct 248 ms 127132 KB Output is correct
23 Correct 315 ms 133488 KB Output is correct
24 Correct 189 ms 114404 KB Output is correct
25 Correct 214 ms 111556 KB Output is correct
26 Correct 306 ms 135600 KB Output is correct
27 Correct 276 ms 130852 KB Output is correct
28 Correct 190 ms 103236 KB Output is correct
29 Correct 462 ms 135036 KB Output is correct
30 Correct 292 ms 107396 KB Output is correct
31 Correct 291 ms 106924 KB Output is correct
32 Correct 531 ms 73028 KB Output is correct
33 Correct 587 ms 93728 KB Output is correct
34 Correct 629 ms 103888 KB Output is correct
35 Correct 578 ms 99112 KB Output is correct
36 Correct 628 ms 109088 KB Output is correct
37 Correct 531 ms 74000 KB Output is correct
38 Correct 998 ms 140136 KB Output is correct
39 Correct 874 ms 119048 KB Output is correct
40 Correct 940 ms 148896 KB Output is correct
41 Correct 990 ms 148784 KB Output is correct
42 Correct 952 ms 127432 KB Output is correct
43 Correct 564 ms 64564 KB Output is correct
44 Correct 527 ms 63468 KB Output is correct
45 Correct 527 ms 59644 KB Output is correct
46 Correct 573 ms 81068 KB Output is correct
47 Correct 844 ms 108724 KB Output is correct
48 Correct 871 ms 121688 KB Output is correct
49 Correct 861 ms 111172 KB Output is correct
50 Correct 1022 ms 141744 KB Output is correct
51 Correct 416 ms 103848 KB Output is correct
52 Correct 471 ms 113764 KB Output is correct
53 Correct 411 ms 105008 KB Output is correct