oj.uz

Submission #1045774

# Submission time Handle Problem Language Result Execution time Memory
1045774 2024-08-06T07:35:01 Z javotaz Dabbeh (INOI20_dabbeh) C++17
25 / 100
 335 ms 65712 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 * N], b[N];
ll h[N], rtb[N];
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 4 ms 31576 KB Output is correct
2 Correct 151 ms 52564 KB Output is correct
3 Correct 112 ms 47736 KB Output is correct
4 Correct 146 ms 52304 KB Output is correct
5 Correct 123 ms 50756 KB Output is correct
6 Correct 165 ms 55376 KB Output is correct
7 Correct 123 ms 57624 KB Output is correct
8 Correct 212 ms 56916 KB Output is correct
9 Correct 131 ms 54608 KB Output is correct
10 Correct 65 ms 39252 KB Output is correct
11 Correct 50 ms 55784 KB Output is correct
12 Correct 41 ms 44344 KB Output is correct
13 Correct 46 ms 50660 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31576 KB Output is correct
2 Correct 151 ms 52564 KB Output is correct
3 Correct 112 ms 47736 KB Output is correct
4 Correct 146 ms 52304 KB Output is correct
5 Correct 123 ms 50756 KB Output is correct
6 Correct 165 ms 55376 KB Output is correct
7 Correct 123 ms 57624 KB Output is correct
8 Correct 212 ms 56916 KB Output is correct
9 Correct 131 ms 54608 KB Output is correct
10 Correct 65 ms 39252 KB Output is correct
11 Correct 50 ms 55784 KB Output is correct
12 Correct 41 ms 44344 KB Output is correct
13 Correct 46 ms 50660 KB Output is correct
14 Incorrect 335 ms 65712 KB Output isn't correct
15 Halted 0 ms 0 KB -