Submission #1045827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045827		javotaz	Dabbeh (INOI20_dabbeh)	C++17	100 / 100	425 ms	125440 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, mod1 = 1000992299, base1 = 760, mod2 = 1e9 + 9, base2 = 600;
string s, a[M];
int n, q, p[N][LG], m, mx[2 * N], b[N];
ll h1[N], h2[N], rtb1[N], rtb2[N];
unordered_set<int64_t> st[K];

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

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

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

void solve() {
	for (int i = 0; i < n; i++) {
		ll v1 = 0, tb1 = 1, v2 = 0, tb2 = 1;
		for (int j = 0; j < a[i].size(); j++) {
			v1 = (v1 + tb1 * a[i][j]) % mod1;
			tb1 = tb1 * base1 % mod1;
			v2 = (v2 + tb2 * a[i][j]) % mod2;
			tb2 = tb2 * base2 % mod2;
			st[j + 1].insert((v1 << 31) | v2);
		}
	}
	ll rb1 = bp1(base1, mod1 - 2);
	rtb1[0] = 1;
	for (int i = 1; i <= m; i++)
		rtb1[i] = rtb1[i - 1] * rb1 % mod1;
	ll tb1 = 1;
	for (int i = 1; i <= m; i++)
		h1[i] = (h1[i - 1] + s[i - 1] * tb1) % mod1, tb1 = tb1 * base1 % mod1;
	ll rb2 = bp2(base2, mod2 - 2);
	rtb2[0] = 1;
	for (int i = 1; i <= m; i++)
		rtb2[i] = rtb2[i - 1] * rb2 % mod2;
	ll tb2 = 1;
	for (int i = 1; i <= m; i++)
		h2[i] = (h2[i - 1] + s[i - 1] * tb2) % mod2, tb2 = tb2 * base2 % mod2;
	for (int i = 0; i < m; ++i) {
		int l = i, r = m + 1;
		while (r - l > 1) {
			int mid = (l + r) >> 1;
			ll v1 = (h1[mid] - h1[i] + mod1) * rtb1[i] % mod1;
			ll v2 = (h2[mid] - h2[i] + mod2) * rtb2[i] % mod2;
			if (st[mid - i].count((v1 << 31) | v2))
				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:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for (int j = 0; j < a[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50