oj.uz

Submission #1045746

# Submission time Handle Problem Language Result Execution time Memory
1045746 2024-08-06T07:21:45 Z javotaz Dabbeh (INOI20_dabbeh) C++17
25 / 100
 122 ms 95740 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 = 19, 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 33624 KB Output is correct
2 Correct 95 ms 51052 KB Output is correct
3 Correct 87 ms 46676 KB Output is correct
4 Correct 104 ms 50516 KB Output is correct
5 Correct 92 ms 49116 KB Output is correct
6 Correct 115 ms 53328 KB Output is correct
7 Correct 109 ms 56860 KB Output is correct
8 Correct 122 ms 54500 KB Output is correct
9 Correct 97 ms 52300 KB Output is correct
10 Correct 58 ms 38736 KB Output is correct
11 Correct 82 ms 95740 KB Output is correct
12 Correct 57 ms 63200 KB Output is correct
13 Correct 89 ms 81208 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 63824 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 33624 KB Output is correct
2 Correct 95 ms 51052 KB Output is correct
3 Correct 87 ms 46676 KB Output is correct
4 Correct 104 ms 50516 KB Output is correct
5 Correct 92 ms 49116 KB Output is correct
6 Correct 115 ms 53328 KB Output is correct
7 Correct 109 ms 56860 KB Output is correct
8 Correct 122 ms 54500 KB Output is correct
9 Correct 97 ms 52300 KB Output is correct
10 Correct 58 ms 38736 KB Output is correct
11 Correct 82 ms 95740 KB Output is correct
12 Correct 57 ms 63200 KB Output is correct
13 Correct 89 ms 81208 KB Output is correct
14 Incorrect 112 ms 63824 KB Output isn't correct
15 Halted 0 ms 0 KB -