Submission #469069

#	Time	Username	Problem	Language	Result	Execution time	Memory
469069		sinamhdv	Dabbeh (INOI20_dabbeh)	C++11	50 / 100	2091 ms	108156 KiB

Main

// INOI20_dabbeh
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod[] = {1000010549, 1000 * 1000 * 1000 + 7};
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
const int prm[] = {727, 883};

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int MAXN = 300100;
const int LOGN = 22;

struct chash
{
	ll operator()(const pii &p) const
	{
		return (ll)p.fr * 1000000000 + p.sc;
	}
};

int n, q;
char s[MAXN];
gp_hash_table<pii, bool, chash> st;
int pw[2][MAXN];
int hsh[2][MAXN];
int dp[LOGN][MAXN];

inline int gethash(int t, int l, int r)
{
	return (mod[t] + (hsh[t][r + 1] - hsh[t][l] * (ll)pw[t][r - l + 1]) % mod[t]) % mod[t];
}
#define gethashpr(l, r) {gethash(0, (l), (r)), gethash(1, (l), (r))}

struct SEG
{
	int seg[2 * MAXN];

	inline void build(int *dp)
	{
		FOR(i, 0, MAXN) seg[i + MAXN] = dp[i];
		for (int i = MAXN - 1; i > 0; i--) seg[i] = max(seg[2 * i], seg[2 * i + 1]);
	}

	inline int get(int l, int r)
	{
		r++;
		int res = -INF;
		for (l += MAXN, r += MAXN; l < r; l /= 2, r /= 2)
		{
			if (l % 2) res = max(res, seg[l++]);
			if (r % 2) res = max(res, seg[--r]);
		}
		return res;
	}

} seg[LOGN];

int32_t main(void)
{
	fast_io;
	int tmp;
	cin >> tmp >> q;
	while (tmp--)
	{
		string t;
		cin >> t;
		int h[2] = {};
		for (char c : t)
		{
			FOR(t, 0, 2)
				h[t] = (h[t] * (ll)prm[t] + c) % mod[t];
			st.insert({{h[0], h[1]}, 0});
		}
	}
	
	cin >> s;
	n = strlen(s);

	FOR(t, 0, 2)
	{
		pw[t][0] = 1;
		FOR(i, 1, MAXN) pw[t][i] = pw[t][i - 1] * (ll)prm[t] % mod[t];
		FOR(i, 1, n + 1) hsh[t][i] = (hsh[t][i - 1] * (ll)prm[t] + s[i - 1]) % mod[t];
	}

	FOR(i, 0, n)
	{
		int l = 0, r = n - i + 1;
		while (r - l > 1)
		{
			int mid = (r + l) / 2;
			if (st.find(gethashpr(i, i + mid - 1)) != st.end()) l = mid;
			else r = mid;
		}
		dp[0][i] = i + l - 1;
	}

	FOR(i, 1, LOGN)
	{
		seg[i - 1].build(dp[i - 1]);
		FOR(j, 0, n)
		{
			dp[i][j] = seg[i - 1].get(j, dp[i - 1][j] + 1);
		}
	}
	seg[LOGN - 1].build(dp[LOGN - 1]);

	while (q--)
	{
		int l, r;
		cin >> l >> r;
		r--;
		int ptr = l;
		int cost = 0;
		for (int i = LOGN - 1; i >= 0; i--)
		{
			int fw = seg[i].get(l, ptr);
			if (fw >= r) continue;
			cost += (1 << i);
			ptr = fw + 1;
		}
		if (cost > n) cout << "-1\n";
		else cout << cost + 1 << endl;
	}

	return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 0 / 50