oj.uz

Submission #469069

# Submission time Handle Problem Language Result Execution time Memory
469069 2021-08-30T15:38:01 Z sinamhdv Dabbeh (INOI20_dabbeh) C++11
50 / 100
 2000 ms 108156 KB 
// 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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 54468 KB Output is correct
2 Correct 265 ms 79816 KB Output is correct
3 Correct 281 ms 80024 KB Output is correct
4 Correct 303 ms 80036 KB Output is correct
5 Correct 314 ms 80148 KB Output is correct
6 Correct 349 ms 80104 KB Output is correct
7 Correct 345 ms 80120 KB Output is correct
8 Correct 324 ms 79952 KB Output is correct
9 Correct 285 ms 80000 KB Output is correct
10 Correct 218 ms 61376 KB Output is correct
11 Correct 207 ms 79820 KB Output is correct
12 Correct 177 ms 67460 KB Output is correct
13 Correct 200 ms 79704 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 750 ms 95136 KB Output is correct
2 Correct 942 ms 108016 KB Output is correct
3 Correct 818 ms 95528 KB Output is correct
4 Correct 658 ms 89424 KB Output is correct
5 Correct 896 ms 89364 KB Output is correct
6 Correct 911 ms 108004 KB Output is correct
7 Correct 932 ms 108100 KB Output is correct
8 Correct 850 ms 95772 KB Output is correct
9 Correct 920 ms 107996 KB Output is correct
10 Correct 962 ms 108116 KB Output is correct
11 Correct 836 ms 95640 KB Output is correct
12 Correct 877 ms 95540 KB Output is correct
13 Correct 969 ms 108116 KB Output is correct
14 Correct 1002 ms 108156 KB Output is correct
15 Correct 682 ms 84712 KB Output is correct
16 Correct 855 ms 108136 KB Output is correct
17 Correct 778 ms 89360 KB Output is correct
18 Correct 798 ms 89364 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 54468 KB Output is correct
2 Correct 265 ms 79816 KB Output is correct
3 Correct 281 ms 80024 KB Output is correct
4 Correct 303 ms 80036 KB Output is correct
5 Correct 314 ms 80148 KB Output is correct
6 Correct 349 ms 80104 KB Output is correct
7 Correct 345 ms 80120 KB Output is correct
8 Correct 324 ms 79952 KB Output is correct
9 Correct 285 ms 80000 KB Output is correct
10 Correct 218 ms 61376 KB Output is correct
11 Correct 207 ms 79820 KB Output is correct
12 Correct 177 ms 67460 KB Output is correct
13 Correct 200 ms 79704 KB Output is correct
14 Correct 750 ms 95136 KB Output is correct
15 Correct 942 ms 108016 KB Output is correct
16 Correct 818 ms 95528 KB Output is correct
17 Correct 658 ms 89424 KB Output is correct
18 Correct 896 ms 89364 KB Output is correct
19 Correct 911 ms 108004 KB Output is correct
20 Correct 932 ms 108100 KB Output is correct
21 Correct 850 ms 95772 KB Output is correct
22 Correct 920 ms 107996 KB Output is correct
23 Correct 962 ms 108116 KB Output is correct
24 Correct 836 ms 95640 KB Output is correct
25 Correct 877 ms 95540 KB Output is correct
26 Correct 969 ms 108116 KB Output is correct
27 Correct 1002 ms 108156 KB Output is correct
28 Correct 682 ms 84712 KB Output is correct
29 Correct 855 ms 108136 KB Output is correct
30 Correct 778 ms 89360 KB Output is correct
31 Correct 798 ms 89364 KB Output is correct
32 Correct 1383 ms 79316 KB Output is correct
33 Correct 1484 ms 89852 KB Output is correct
34 Correct 1497 ms 102204 KB Output is correct
35 Correct 1432 ms 102316 KB Output is correct
36 Correct 1451 ms 102260 KB Output is correct
37 Correct 1371 ms 80464 KB Output is correct
38 Execution timed out 2091 ms 105016 KB Time limit exceeded
39 Halted 0 ms 0 KB -