Submission #623694

#	Time	Username	Problem	Language	Result	Execution time	Memory
623694		Arinoor	Dabbeh (INOI20_dabbeh)	C++17	100 / 100	1022 ms	148896 KiB

Main

#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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50