oj.uz

Submission #773862

# Submission time Handle Problem Language Result Execution time Memory
773862 2023-07-05T09:12:03 Z parsadox2 Dabbeh (INOI20_dabbeh) C++14
100 / 100
 1452 ms 68040 KB 
#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define wall 		cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e5 + 10 , Base = 727 , maxl = 20;
int n , L , m , pw[2][maxn] , mod[2] , prehsh[2][maxn] , rr[maxn];
pair<int , int> ar[maxn] , adj[maxl][maxn];
int modit(int ty , int a)
{
	if(a >= mod[ty])  return a - mod[ty];
	return a;
}

pair<int , int> get(int l , int r)
{
	int res[2];
	if(l == 0)  return make_pair(prehsh[0][r] , prehsh[1][r]);
	for(int ty = 0 ; ty < 2 ; ty++)
	{
		res[ty] = 1LL * prehsh[ty][l - 1] * pw[ty][r - l + 1] % mod[ty];
		res[ty] = modit(ty , prehsh[ty][r] + mod[ty] - res[ty]);
	}
	return make_pair(res[0] , res[1]);
}

int solve(int l , int r)
{
	if(adj[maxl - 1][l].S < r)  return -1;
	int res = 0;
	for(int i = maxl - 2 ; i > -1 ; i--)  if(adj[i][l].S < r)
	{
		res |= (1 << i);
		l = adj[i][l].F;
	}
	res++;
	return res;
}

int32_t main()
{
	fast;
	mod[0] = 1e9 + 7;
	mod[1] = 998244353;
	pw[0][0] = pw[1][0] = 1;
	for(int i = 1 ; i < maxn ; i++)  for(int ty = 0 ; ty < 2 ; ty++)
		pw[ty][i] = 1LL * pw[ty][i - 1] * Base % mod[ty];
	cin >> n >> m;
	vector <pair<int , int>> vec;
	for(int i = 0 ; i < n ; i++)
	{
		string t;  cin >> t;
		int hsh[2];
		hsh[0] = hsh[1] = 0;
		for(int j = 0 ; j < SZ(t) ; j++)
		{
			for(int ty = 0 ; ty < 2 ; ty++)
			{
				hsh[ty] = 1LL * hsh[ty] * Base % mod[ty];
				hsh[ty] = modit(ty , hsh[ty] + t[j]);
			}
			vec.pb({hsh[0] , hsh[1]});
		}
	}
	sort(vec.begin() , vec.end());
	vec.resize(unique(vec.begin() , vec.end()) - vec.begin());
	string s;  cin >> s;
	L = SZ(s);
	for(int i = 0 ; i < m ; i++)  cin >> ar[i].F >> ar[i].S;
	prehsh[0][0] = prehsh[1][0] = s[0];
	for(int i = 1 ; i < L ; i++)  for(int ty = 0 ; ty < 2 ; ty++)
	{
		prehsh[ty][i] = 1LL * prehsh[ty][i - 1] * Base % mod[ty];
		prehsh[ty][i] = modit(ty , prehsh[ty][i] + s[i]);
	}
	for(int i = 0 ; i < L ; i++)
	{
		int low = i - 1 , high = L;
		while(high - low > 1)
		{
			int mid = (high + low) >> 1;
			auto now = get(i , mid);
			int it = lower_bound(vec.begin() , vec.end() , now) - vec.begin();
			if(vec[it] == now)  low = mid;
			else  high = mid;
		}
		rr[i] = high;
	}
	vector <int> st;
	adj[0][L] = {L , L};
	rr[L] = L;
	st.pb(L);
	for(int i = L - 1 ; i > -1 ; i--)
	{
		if(rr[i] == i)
		{
			adj[0][i] = {i , i};
			st.pb(i);
			continue;
		}
		int low = -1 , high = SZ(st);
		while(high - low > 1)
		{
			int mid = (high + low) >> 1;
			if(st[mid] <= rr[i])  high = mid;
			else  low = mid;
		}
		adj[0][i] = {st[high] , rr[i]};
		while(!st.empty() && rr[i] >= rr[st.back()])  st.pop_back();
		st.pb(i);
	}
	for(int i = 1 ; i < maxl ; i++)
		for(int j = 0 ; j <= L ; j++)
			adj[i][j] = adj[i - 1][adj[i - 1][j].F];
	for(int i = 0 ; i < m ; i++)
		cout << solve(ar[i].F , ar[i].S) << '\n';
	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 92 ms 11180 KB Output is correct
3 Correct 90 ms 10808 KB Output is correct
4 Correct 99 ms 11820 KB Output is correct
5 Correct 100 ms 11440 KB Output is correct
6 Correct 104 ms 12504 KB Output is correct
7 Correct 116 ms 12696 KB Output is correct
8 Correct 110 ms 12632 KB Output is correct
9 Correct 105 ms 12112 KB Output is correct
10 Correct 83 ms 9356 KB Output is correct
11 Correct 96 ms 12096 KB Output is correct
12 Correct 70 ms 10024 KB Output is correct
13 Correct 84 ms 11160 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 57200 KB Output is correct
2 Correct 855 ms 58384 KB Output is correct
3 Correct 765 ms 57488 KB Output is correct
4 Correct 713 ms 56816 KB Output is correct
5 Correct 685 ms 56412 KB Output is correct
6 Correct 830 ms 58476 KB Output is correct
7 Correct 870 ms 58860 KB Output is correct
8 Correct 837 ms 58084 KB Output is correct
9 Correct 867 ms 58464 KB Output is correct
10 Correct 969 ms 58984 KB Output is correct
11 Correct 793 ms 57540 KB Output is correct
12 Correct 779 ms 57076 KB Output is correct
13 Correct 921 ms 59424 KB Output is correct
14 Correct 899 ms 58984 KB Output is correct
15 Correct 633 ms 56252 KB Output is correct
16 Correct 873 ms 57676 KB Output is correct
17 Correct 645 ms 56736 KB Output is correct
18 Correct 606 ms 56496 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 92 ms 11180 KB Output is correct
3 Correct 90 ms 10808 KB Output is correct
4 Correct 99 ms 11820 KB Output is correct
5 Correct 100 ms 11440 KB Output is correct
6 Correct 104 ms 12504 KB Output is correct
7 Correct 116 ms 12696 KB Output is correct
8 Correct 110 ms 12632 KB Output is correct
9 Correct 105 ms 12112 KB Output is correct
10 Correct 83 ms 9356 KB Output is correct
11 Correct 96 ms 12096 KB Output is correct
12 Correct 70 ms 10024 KB Output is correct
13 Correct 84 ms 11160 KB Output is correct
14 Correct 782 ms 57200 KB Output is correct
15 Correct 855 ms 58384 KB Output is correct
16 Correct 765 ms 57488 KB Output is correct
17 Correct 713 ms 56816 KB Output is correct
18 Correct 685 ms 56412 KB Output is correct
19 Correct 830 ms 58476 KB Output is correct
20 Correct 870 ms 58860 KB Output is correct
21 Correct 837 ms 58084 KB Output is correct
22 Correct 867 ms 58464 KB Output is correct
23 Correct 969 ms 58984 KB Output is correct
24 Correct 793 ms 57540 KB Output is correct
25 Correct 779 ms 57076 KB Output is correct
26 Correct 921 ms 59424 KB Output is correct
27 Correct 899 ms 58984 KB Output is correct
28 Correct 633 ms 56252 KB Output is correct
29 Correct 873 ms 57676 KB Output is correct
30 Correct 645 ms 56736 KB Output is correct
31 Correct 606 ms 56496 KB Output is correct
32 Correct 779 ms 43296 KB Output is correct
33 Correct 842 ms 46180 KB Output is correct
34 Correct 907 ms 47144 KB Output is correct
35 Correct 801 ms 46608 KB Output is correct
36 Correct 816 ms 46832 KB Output is correct
37 Correct 664 ms 43732 KB Output is correct
38 Correct 1452 ms 67404 KB Output is correct
39 Correct 1250 ms 65328 KB Output is correct
40 Correct 1386 ms 68040 KB Output is correct
41 Correct 1387 ms 67140 KB Output is correct
42 Correct 1241 ms 66568 KB Output is correct
43 Correct 495 ms 30600 KB Output is correct
44 Correct 429 ms 30376 KB Output is correct
45 Correct 456 ms 29860 KB Output is correct
46 Correct 533 ms 31548 KB Output is correct
47 Correct 1298 ms 64400 KB Output is correct
48 Correct 1321 ms 65692 KB Output is correct
49 Correct 1182 ms 63596 KB Output is correct
50 Correct 1312 ms 67700 KB Output is correct
51 Correct 520 ms 62028 KB Output is correct
52 Correct 773 ms 63552 KB Output is correct
53 Correct 567 ms 62132 KB Output is correct