Submission #635593

#	Time	Username	Problem	Language	Result	Execution time	Memory
635593		NothingXD	Dabbeh (INOI20_dabbeh)	C++17	100 / 100	749 ms	130196 KiB

Main

#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 (stderr)

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