Submission #1045756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045756		javotaz	Dabbeh (INOI20_dabbeh)	C++17	25 / 100	141 ms	98024 KiB

Main

// 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 (stderr)

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 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 50