oj.uz

Submission #1045827

# Submission time Handle Problem Language Result Execution time Memory
1045827 2024-08-06T07:58:30 Z javotaz Dabbeh (INOI20_dabbeh) C++17
100 / 100
 425 ms 125440 KB 
// In the Name of Allah
 
#include<bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,avx,avx2,sse4.2,popcnt,tune=native")
 
typedef long long ll;
 
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
#define MX(x, y) ((b[x] > b[y])? x : y)

const int LG = 21, N = 3e5 + 7, M = 1e4 + 7, K = 5e5 + 7, mod1 = 1000992299, base1 = 760, mod2 = 1e9 + 9, base2 = 600;
string s, a[M];
int n, q, p[N][LG], m, mx[2 * N], b[N];
ll h1[N], h2[N], rtb1[N], rtb2[N];
unordered_set<int64_t> st[K];

void ip() {
	cin >> n >> q;
	for (int i = 0; i < n; i++) 
		cin >> a[i];
	cin >> s;
	m = s.size();
}

int bp1(int x, int y) {
	if (y < 2) return y? x : 1;
	ll tmp = bp1(x, y / 2);
	tmp = tmp * tmp % mod1;
	return (y & 1)? tmp * x % mod1 : tmp;
}

int bp2(int x, int y) {
	if (y < 2) return y? x : 1;
	ll tmp = bp2(x, y / 2);
	tmp = tmp * tmp % mod2;
	return (y & 1)? tmp * x % mod2 : tmp;
}

void solve() {
	for (int i = 0; i < n; i++) {
		ll v1 = 0, tb1 = 1, v2 = 0, tb2 = 1;
		for (int j = 0; j < a[i].size(); j++) {
			v1 = (v1 + tb1 * a[i][j]) % mod1;
			tb1 = tb1 * base1 % mod1;
			v2 = (v2 + tb2 * a[i][j]) % mod2;
			tb2 = tb2 * base2 % mod2;
			st[j + 1].insert((v1 << 31) | v2);
		}
	}
	ll rb1 = bp1(base1, mod1 - 2);
	rtb1[0] = 1;
	for (int i = 1; i <= m; i++)
		rtb1[i] = rtb1[i - 1] * rb1 % mod1;
	ll tb1 = 1;
	for (int i = 1; i <= m; i++)
		h1[i] = (h1[i - 1] + s[i - 1] * tb1) % mod1, tb1 = tb1 * base1 % mod1;
	ll rb2 = bp2(base2, mod2 - 2);
	rtb2[0] = 1;
	for (int i = 1; i <= m; i++)
		rtb2[i] = rtb2[i - 1] * rb2 % mod2;
	ll tb2 = 1;
	for (int i = 1; i <= m; i++)
		h2[i] = (h2[i - 1] + s[i - 1] * tb2) % mod2, tb2 = tb2 * base2 % mod2;
	for (int i = 0; i < m; ++i) {
		int l = i, r = m + 1;
		while (r - l > 1) {
			int mid = (l + r) >> 1;
			ll v1 = (h1[mid] - h1[i] + mod1) * rtb1[i] % mod1;
			ll v2 = (h2[mid] - h2[i] + mod2) * rtb2[i] % mod2;
			if (st[mid - i].count((v1 << 31) | v2))
				l = mid;
			else
				r = mid;
		}
		b[i] = l;
		mx[m + i] = i;
	}
	for (int i = m - 1; i; --i) 
		mx[i] = MX(mx[i << 1], mx[i << 1 | 1]);
	for (int i = m - 1; ~i; --i) {
		int res = i;
		for (int l = i + m, r = min(b[i] + 1, m) + m; l < r; l >>= 1, r >>= 1) {
			if (l & 1) res = MX(res, mx[l]), l++;
			if (r & 1) r--, res = MX(res, mx[r]);
		}
		p[i][0] = res;
		for (int j = 1; j < LG; ++j)
			p[i][j] = p[p[i][j - 1]][j - 1];
	}
	while (q--) {
		int l, r;
		cin >> l >> r;
		if (b[l] >= r) {
			cout << 1 << '\n';
			continue;
		}
		int res = 0;
		for (int i = LG - 1; ~i; --i)
			if (b[p[l][i]] < r)
				res |= (1 << i), l = p[l][i];
		cout << ((res > m)? -1 : res + 2) << '\n';
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ip(), solve();
	return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for (int j = 0; j < a[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 37720 KB Output is correct
2 Correct 133 ms 55284 KB Output is correct
3 Correct 97 ms 50720 KB Output is correct
4 Correct 119 ms 54580 KB Output is correct
5 Correct 95 ms 53188 KB Output is correct
6 Correct 139 ms 57404 KB Output is correct
7 Correct 129 ms 60972 KB Output is correct
8 Correct 167 ms 58708 KB Output is correct
9 Correct 126 ms 56400 KB Output is correct
10 Correct 63 ms 42692 KB Output is correct
11 Correct 132 ms 100072 KB Output is correct
12 Correct 97 ms 67336 KB Output is correct
13 Correct 94 ms 85224 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 73396 KB Output is correct
2 Correct 244 ms 78376 KB Output is correct
3 Correct 190 ms 74632 KB Output is correct
4 Correct 150 ms 69756 KB Output is correct
5 Correct 153 ms 69520 KB Output is correct
6 Correct 246 ms 79304 KB Output is correct
7 Correct 276 ms 81324 KB Output is correct
8 Correct 233 ms 76656 KB Output is correct
9 Correct 230 ms 79768 KB Output is correct
10 Correct 299 ms 83368 KB Output is correct
11 Correct 174 ms 74624 KB Output is correct
12 Correct 201 ms 73180 KB Output is correct
13 Correct 331 ms 84836 KB Output is correct
14 Correct 259 ms 82740 KB Output is correct
15 Correct 124 ms 67832 KB Output is correct
16 Correct 157 ms 125440 KB Output is correct
17 Correct 118 ms 84092 KB Output is correct
18 Correct 124 ms 83648 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 37720 KB Output is correct
2 Correct 133 ms 55284 KB Output is correct
3 Correct 97 ms 50720 KB Output is correct
4 Correct 119 ms 54580 KB Output is correct
5 Correct 95 ms 53188 KB Output is correct
6 Correct 139 ms 57404 KB Output is correct
7 Correct 129 ms 60972 KB Output is correct
8 Correct 167 ms 58708 KB Output is correct
9 Correct 126 ms 56400 KB Output is correct
10 Correct 63 ms 42692 KB Output is correct
11 Correct 132 ms 100072 KB Output is correct
12 Correct 97 ms 67336 KB Output is correct
13 Correct 94 ms 85224 KB Output is correct
14 Correct 173 ms 73396 KB Output is correct
15 Correct 244 ms 78376 KB Output is correct
16 Correct 190 ms 74632 KB Output is correct
17 Correct 150 ms 69756 KB Output is correct
18 Correct 153 ms 69520 KB Output is correct
19 Correct 246 ms 79304 KB Output is correct
20 Correct 276 ms 81324 KB Output is correct
21 Correct 233 ms 76656 KB Output is correct
22 Correct 230 ms 79768 KB Output is correct
23 Correct 299 ms 83368 KB Output is correct
24 Correct 174 ms 74624 KB Output is correct
25 Correct 201 ms 73180 KB Output is correct
26 Correct 331 ms 84836 KB Output is correct
27 Correct 259 ms 82740 KB Output is correct
28 Correct 124 ms 67832 KB Output is correct
29 Correct 157 ms 125440 KB Output is correct
30 Correct 118 ms 84092 KB Output is correct
31 Correct 124 ms 83648 KB Output is correct
32 Correct 158 ms 64204 KB Output is correct
33 Correct 314 ms 73236 KB Output is correct
34 Correct 301 ms 78232 KB Output is correct
35 Correct 306 ms 76128 KB Output is correct
36 Correct 285 ms 81344 KB Output is correct
37 Correct 201 ms 63760 KB Output is correct
38 Correct 407 ms 89576 KB Output is correct
39 Correct 346 ms 79692 KB Output is correct
40 Correct 408 ms 92340 KB Output is correct
41 Correct 410 ms 92940 KB Output is correct
42 Correct 334 ms 84440 KB Output is correct
43 Correct 199 ms 64592 KB Output is correct
44 Correct 190 ms 63516 KB Output is correct
45 Correct 194 ms 63004 KB Output is correct
46 Correct 230 ms 70764 KB Output is correct
47 Correct 252 ms 74628 KB Output is correct
48 Correct 339 ms 80920 KB Output is correct
49 Correct 272 ms 75436 KB Output is correct
50 Correct 425 ms 90780 KB Output is correct
51 Correct 129 ms 76480 KB Output is correct
52 Correct 174 ms 91888 KB Output is correct
53 Correct 130 ms 78152 KB Output is correct