oj.uz

Submission #1045762

# Submission time Handle Problem Language Result Execution time Memory
1045762 2024-08-06T07:29:24 Z javotaz Dabbeh (INOI20_dabbeh) C++17
25 / 100
 141 ms 98276 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];
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 35672 KB Output is correct
2 Correct 101 ms 53136 KB Output is correct
3 Correct 99 ms 48724 KB Output is correct
4 Correct 108 ms 52744 KB Output is correct
5 Correct 87 ms 51032 KB Output is correct
6 Correct 137 ms 55380 KB Output is correct
7 Correct 109 ms 58832 KB Output is correct
8 Correct 141 ms 56916 KB Output is correct
9 Correct 135 ms 54684 KB Output is correct
10 Correct 74 ms 40788 KB Output is correct
11 Correct 83 ms 98276 KB Output is correct
12 Correct 62 ms 65500 KB Output is correct
13 Correct 74 ms 83624 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 68532 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 35672 KB Output is correct
2 Correct 101 ms 53136 KB Output is correct
3 Correct 99 ms 48724 KB Output is correct
4 Correct 108 ms 52744 KB Output is correct
5 Correct 87 ms 51032 KB Output is correct
6 Correct 137 ms 55380 KB Output is correct
7 Correct 109 ms 58832 KB Output is correct
8 Correct 141 ms 56916 KB Output is correct
9 Correct 135 ms 54684 KB Output is correct
10 Correct 74 ms 40788 KB Output is correct
11 Correct 83 ms 98276 KB Output is correct
12 Correct 62 ms 65500 KB Output is correct
13 Correct 74 ms 83624 KB Output is correct
14 Incorrect 119 ms 68532 KB Output isn't correct
15 Halted 0 ms 0 KB -