oj.uz

Submission #1045756

# Submission time Handle Problem Language Result Execution time Memory
1045756 2024-08-06T07:26:21 Z javotaz Dabbeh (INOI20_dabbeh) C++17
25 / 100
 141 ms 98024 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, mod = 1e9 + 9, base = 760;
string s, a[M];
int n, q, p[N][LG], m, mx[2 * M], b[N];
ll h[N], rtb[N];
unordered_set<int> st[K];

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

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

void solve() {
	for (int i = 0; i < n; i++) {
		ll v = 0, tb = 1;
		for (int j = 0; j < a[i].size(); j++) {
			v = (v + tb * a[i][j]) % mod;
			tb = tb * base % mod;
			st[j + 1].insert(v);
		}
	}
	ll rb = bp(base, mod - 2);
	rtb[0] = 1;
	for (int i = 1; i <= m; i++)
		rtb[i] = rtb[i - 1] * rb % mod;
	ll tb = 1;
	for (int i = 1; i <= m; i++)
		h[i] = (h[i - 1] + s[i - 1] * tb) % mod, tb = tb * base % mod;
	for (int i = 0; i < m; ++i) {
		int l = i, r = m + 1;
		while (r - l > 1) {
			int mid = (l + r) >> 1;
			if (st[mid - i].count((h[mid] - h[i] + mod) * rtb[i] % mod))
				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:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   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 33628 KB Output is correct
2 Correct 120 ms 53052 KB Output is correct
3 Correct 105 ms 48980 KB Output is correct
4 Correct 111 ms 52816 KB Output is correct
5 Correct 89 ms 51404 KB Output is correct
6 Correct 122 ms 55636 KB Output is correct
7 Correct 101 ms 59216 KB Output is correct
8 Correct 141 ms 56912 KB Output is correct
9 Correct 124 ms 54608 KB Output is correct
10 Correct 59 ms 41044 KB Output is correct
11 Correct 79 ms 98024 KB Output is correct
12 Correct 63 ms 65500 KB Output is correct
13 Correct 109 ms 83560 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 66736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33628 KB Output is correct
2 Correct 120 ms 53052 KB Output is correct
3 Correct 105 ms 48980 KB Output is correct
4 Correct 111 ms 52816 KB Output is correct
5 Correct 89 ms 51404 KB Output is correct
6 Correct 122 ms 55636 KB Output is correct
7 Correct 101 ms 59216 KB Output is correct
8 Correct 141 ms 56912 KB Output is correct
9 Correct 124 ms 54608 KB Output is correct
10 Correct 59 ms 41044 KB Output is correct
11 Correct 79 ms 98024 KB Output is correct
12 Correct 63 ms 65500 KB Output is correct
13 Correct 109 ms 83560 KB Output is correct
14 Incorrect 120 ms 66736 KB Output isn't correct
15 Halted 0 ms 0 KB -