oj.uz

Submission #635593

# Submission time Handle Problem Language Result Execution time Memory
635593 2022-08-26T13:34:09 Z NothingXD Dabbeh (INOI20_dabbeh) C++17
100 / 100
 749 ms 130196 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int maxn = 1e6 + 10;
const int lg = 20;
int n, q, a[maxn], sz, suf[maxn], tmp[maxn], cnt[maxn], rnk[maxn << 1], l[maxn], r[maxn], lcp[lg][maxn], rmq[lg][maxn], dp[lg][maxn];
int L[maxn], R[maxn], ptr[maxn], ans[maxn];
string s, t;
vector<int> st;
int w = 1;

bool sufcmp(int x, int y){
	return (rnk[x] == rnk[y]? rnk[x+w] < rnk[y+w]: rnk[x] < rnk[y]);
}

void sufarr(string &s){
	int n = s.size();
	for (int i = 0; i < n; i++){
		if (s[i] == '#') continue;
		rnk[i] = s[i] - 'a' + 1;
	}
	for (; ; w <<= 1){
		memset(cnt, 0, sizeof cnt);
		for (int i = 0; i < n; i++){
			cnt[rnk[i+w]]++;
		}
		for (int i = 1; i <= max(26, n); i++){
			cnt[i] += cnt[i-1];
		}
		for (int i = 0; i < n; i++){
			tmp[--cnt[rnk[i+w]]] = i;
		}
		memset(cnt, 0, sizeof cnt);
		for (int i = 0; i < n; i++){
			cnt[rnk[i]]++;
		}
		for (int i = 1; i <= max(26, n); i++){
			cnt[i] += cnt[i-1];
		}
		for (int i = n-1; ~i; i--){
			suf[--cnt[rnk[tmp[i]]]] = tmp[i];
		}
		tmp[suf[0]] = 1;
		for (int i = 1; i < n; i++){
			tmp[suf[i]] = tmp[suf[i-1]] + sufcmp(suf[i-1], suf[i]);
		}
		for (int i = 0; i < n; i++) rnk[i] = tmp[i];
		if (rnk[suf[n-1]] == n) break;
	}
}

void buildlcp(string &s){
	int n = s.size();
	int k = 0;
	for (int i = 0; i < n; i++){
		if (rnk[i] == n) continue;
		while(i + k < n && suf[rnk[i]] + k < n && s[i+k] == s[suf[rnk[i]]+k]) k++;
		lcp[0][rnk[i]] = k;
		if (k) k--;
	}
	for (int i = 1; i < lg; i++){
		for (int j = 1; j + (1 << i) - 1 <= n; j++){
			lcp[i][j] = min(lcp[i-1][j], lcp[i-1][j + (1 << (i-1))]);
		}
	}
}

int getlcp(int l, int r){
	if (r < l) swap(l, r);
	int x = 31 - __builtin_clz(r-l);
	return min(lcp[x][l], lcp[x][r - (1 << x)]);
}

void buildrmq(){
	for (int i = 0; i < sz; i++) rmq[0][i] = a[i];
	for (int i = 1; i < lg; i++){
		for (int j = 0; j + (1 << i) <= sz; j++){
			rmq[i][j] = max(rmq[i-1][j], rmq[i-1][j + (1 << (i-1))]);
		}
	}
}

int getmax(int l, int r){
	r++;
	int x = 31 - __builtin_clz(r-l);
	return max(rmq[x][l], rmq[x][r - (1 << x)]);
}

void solve(){
	for (int i = lg-1; ~i; i--){
		for (int j = 0; j < sz; j++) a[j] = dp[i][j];
		buildrmq();
		for (int j = 1; j <= q; j++){
			if (getmax(L[j], ptr[j]) < R[j]){
				ptr[j] = getmax(L[j], ptr[j]);
				ans[j] += (1 << i);
			}
		}
	}
}

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

	cin >> n >> q;
	for (int i = 1; i <= n; i++){
		string t; cin >> t;
		l[i] = s.size();
		s += t;
		r[i] = s.size();
		s.push_back('#');
	}

	cin >> t;
	sz = t.size();
	l[0] = s.size();
	s += t;
	r[0] = s.size();
	s.push_back('#');
	sufarr(s);
	buildlcp(s);

	for (int i = 1; i <= n; i++){
		st.push_back(rnk[l[i]]);
	}

	sort(all(st));

	for (int i = 0; i < sz; i++){
		int ptr = lower_bound(all(st), rnk[l[0] + i]) - st.begin();
		if (ptr < st.size()) dp[0][i] = max(dp[0][i], min(sz-i, getlcp(rnk[l[0] + i], st[ptr])));
		ptr--;
		if (ptr >= 0) dp[0][i] = max(dp[0][i], min(sz-i, getlcp(st[ptr], rnk[l[0] + i])));
		dp[0][i] += i;
	}

	for (int i = 1; i < lg; i++){
		for (int j = 0; j < sz; j++) a[j] = dp[i-1][j];
		buildrmq();
		for (int j = 0; j < sz; j++){
			if (dp[i-1][j] == sz){
				dp[i][j] = sz;
			}
			else dp[i][j] = getmax(j, dp[i-1][j]);
		}
	}

	for (int i = 1; i <= q; i++){
		cin >> L[i] >> R[i];
		ptr[i] = L[i];
	}

	solve();

	for (int i = 1; i <= q; i++){
		cout << (getmax(L[i], ptr[i]) < R[i]? -1: ans[i] + 1) << '\n';
	}

	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:151:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |   if (ptr < st.size()) dp[0][i] = max(dp[0][i], min(sz-i, getlcp(rnk[l[0] + i], st[ptr])));
      |       ~~~~^~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Output is correct
2 Correct 158 ms 44244 KB Output is correct
3 Correct 161 ms 35112 KB Output is correct
4 Correct 196 ms 45332 KB Output is correct
5 Correct 181 ms 40348 KB Output is correct
6 Correct 216 ms 51016 KB Output is correct
7 Correct 219 ms 52588 KB Output is correct
8 Correct 212 ms 53996 KB Output is correct
9 Correct 200 ms 47956 KB Output is correct
10 Correct 115 ms 20940 KB Output is correct
11 Correct 324 ms 47428 KB Output is correct
12 Correct 198 ms 27340 KB Output is correct
13 Correct 262 ms 38276 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 90168 KB Output is correct
2 Correct 440 ms 102256 KB Output is correct
3 Correct 354 ms 91196 KB Output is correct
4 Correct 334 ms 83288 KB Output is correct
5 Correct 385 ms 84292 KB Output is correct
6 Correct 395 ms 101720 KB Output is correct
7 Correct 458 ms 108396 KB Output is correct
8 Correct 457 ms 98308 KB Output is correct
9 Correct 446 ms 104568 KB Output is correct
10 Correct 510 ms 110572 KB Output is correct
11 Correct 520 ms 92184 KB Output is correct
12 Correct 410 ms 89564 KB Output is correct
13 Correct 499 ms 112660 KB Output is correct
14 Correct 466 ms 108032 KB Output is correct
15 Correct 446 ms 81924 KB Output is correct
16 Correct 648 ms 111760 KB Output is correct
17 Correct 483 ms 85424 KB Output is correct
18 Correct 501 ms 85100 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Output is correct
2 Correct 158 ms 44244 KB Output is correct
3 Correct 161 ms 35112 KB Output is correct
4 Correct 196 ms 45332 KB Output is correct
5 Correct 181 ms 40348 KB Output is correct
6 Correct 216 ms 51016 KB Output is correct
7 Correct 219 ms 52588 KB Output is correct
8 Correct 212 ms 53996 KB Output is correct
9 Correct 200 ms 47956 KB Output is correct
10 Correct 115 ms 20940 KB Output is correct
11 Correct 324 ms 47428 KB Output is correct
12 Correct 198 ms 27340 KB Output is correct
13 Correct 262 ms 38276 KB Output is correct
14 Correct 407 ms 90168 KB Output is correct
15 Correct 440 ms 102256 KB Output is correct
16 Correct 354 ms 91196 KB Output is correct
17 Correct 334 ms 83288 KB Output is correct
18 Correct 385 ms 84292 KB Output is correct
19 Correct 395 ms 101720 KB Output is correct
20 Correct 458 ms 108396 KB Output is correct
21 Correct 457 ms 98308 KB Output is correct
22 Correct 446 ms 104568 KB Output is correct
23 Correct 510 ms 110572 KB Output is correct
24 Correct 520 ms 92184 KB Output is correct
25 Correct 410 ms 89564 KB Output is correct
26 Correct 499 ms 112660 KB Output is correct
27 Correct 466 ms 108032 KB Output is correct
28 Correct 446 ms 81924 KB Output is correct
29 Correct 648 ms 111760 KB Output is correct
30 Correct 483 ms 85424 KB Output is correct
31 Correct 501 ms 85100 KB Output is correct
32 Correct 337 ms 62108 KB Output is correct
33 Correct 473 ms 81644 KB Output is correct
34 Correct 613 ms 91372 KB Output is correct
35 Correct 494 ms 86788 KB Output is correct
36 Correct 472 ms 96380 KB Output is correct
37 Correct 342 ms 62996 KB Output is correct
38 Correct 649 ms 122000 KB Output is correct
39 Correct 578 ms 101716 KB Output is correct
40 Correct 665 ms 129832 KB Output is correct
41 Correct 749 ms 130196 KB Output is correct
42 Correct 706 ms 109724 KB Output is correct
43 Correct 318 ms 61108 KB Output is correct
44 Correct 318 ms 60076 KB Output is correct
45 Correct 287 ms 56588 KB Output is correct
46 Correct 405 ms 76808 KB Output is correct
47 Correct 517 ms 91820 KB Output is correct
48 Correct 573 ms 103780 KB Output is correct
49 Correct 511 ms 94384 KB Output is correct
50 Correct 674 ms 123176 KB Output is correct
51 Correct 554 ms 87256 KB Output is correct
52 Correct 571 ms 96656 KB Output is correct
53 Correct 515 ms 88324 KB Output is correct