oj.uz

답안 #1045764

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1045764 2024-08-06T07:30:50 Z javotaz Dabbeh (INOI20_dabbeh) C++17
25 / 100
 153 ms 100088 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)
#define int ll

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:44:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for (int j = 0; j < a[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 35676 KB Output is correct
2 Correct 99 ms 53088 KB Output is correct
3 Correct 92 ms 50768 KB Output is correct
4 Correct 116 ms 54800 KB Output is correct
5 Correct 99 ms 53072 KB Output is correct
6 Correct 118 ms 57428 KB Output is correct
7 Correct 122 ms 60876 KB Output is correct
8 Correct 121 ms 58704 KB Output is correct
9 Correct 104 ms 56460 KB Output is correct
10 Correct 60 ms 42708 KB Output is correct
11 Correct 153 ms 100088 KB Output is correct
12 Correct 78 ms 67292 KB Output is correct
13 Correct 92 ms 85224 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 133 ms 96736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 35676 KB Output is correct
2 Correct 99 ms 53088 KB Output is correct
3 Correct 92 ms 50768 KB Output is correct
4 Correct 116 ms 54800 KB Output is correct
5 Correct 99 ms 53072 KB Output is correct
6 Correct 118 ms 57428 KB Output is correct
7 Correct 122 ms 60876 KB Output is correct
8 Correct 121 ms 58704 KB Output is correct
9 Correct 104 ms 56460 KB Output is correct
10 Correct 60 ms 42708 KB Output is correct
11 Correct 153 ms 100088 KB Output is correct
12 Correct 78 ms 67292 KB Output is correct
13 Correct 92 ms 85224 KB Output is correct
14 Incorrect 133 ms 96736 KB Output isn't correct
15 Halted 0 ms 0 KB -