oj.uz

Submission #469065

# Submission time Handle Problem Language Result Execution time Memory
469065 2021-08-30T15:25:38 Z sinamhdv Dabbeh (INOI20_dabbeh) C++11
25 / 100
 2000 ms 78440 KB 
// 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, 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;

int n, q;
char s[MAXN];
set<pii> 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]});
		}
	}
	
	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.count(gethashpr(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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 54468 KB Output is correct
2 Correct 442 ms 72852 KB Output is correct
3 Correct 404 ms 67968 KB Output is correct
4 Correct 505 ms 72500 KB Output is correct
5 Correct 492 ms 70944 KB Output is correct
6 Correct 584 ms 75412 KB Output is correct
7 Correct 666 ms 77932 KB Output is correct
8 Correct 619 ms 78440 KB Output is correct
9 Correct 527 ms 76668 KB Output is correct
10 Correct 249 ms 61892 KB Output is correct
11 Correct 479 ms 77744 KB Output is correct
12 Correct 249 ms 66940 KB Output is correct
13 Correct 361 ms 72892 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 27868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 54468 KB Output is correct
2 Correct 442 ms 72852 KB Output is correct
3 Correct 404 ms 67968 KB Output is correct
4 Correct 505 ms 72500 KB Output is correct
5 Correct 492 ms 70944 KB Output is correct
6 Correct 584 ms 75412 KB Output is correct
7 Correct 666 ms 77932 KB Output is correct
8 Correct 619 ms 78440 KB Output is correct
9 Correct 527 ms 76668 KB Output is correct
10 Correct 249 ms 61892 KB Output is correct
11 Correct 479 ms 77744 KB Output is correct
12 Correct 249 ms 66940 KB Output is correct
13 Correct 361 ms 72892 KB Output is correct
14 Execution timed out 2076 ms 27868 KB Time limit exceeded
15 Halted 0 ms 0 KB -