Submission #469060

#	Time	Username	Problem	Language	Result	Execution time	Memory
469060		sinamhdv	Dabbeh (INOI20_dabbeh)	C++11	0 / 100	967 ms	87292 KiB

Main

// INOI20_dabbeh
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000010549;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
const int prm = 727;

#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;

int n, q;
char s[MAXN];
unordered_set<int> st;
int pw[MAXN];
int hsh[MAXN];
int dp[LOGN][MAXN];

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

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 = 0;
		for (char c : t)
		{
			h = (h * (ll)prm + c) % mod;
			st.insert(h);
		}
	}
	
	cin >> s;
	n = strlen(s);

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

	FOR(i, 0, n)
	{
		int l = 0, r = n - i + 1;
		while (r - l > 1)
		{
			int mid = (r + l) / 2;
			if (st.count(gethash(i, i + mid - 1))) 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: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 50