Submission #771002

#	Time	Username	Problem	Language	Result	Execution time	Memory
771002		parsadox2	Dabbeh (INOI20_dabbeh)	C++14	0 / 100	937 ms	435916 KiB

Main

#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 , mod = 1e9 + 7 , Base = 131 , maxl = 20;
int n , m , L , pw[maxn] , prehsh[maxn] , tree[maxl][maxn << 2] , rr[maxn] , ans[maxn];
bitset <mod> marked;
pair<int , int> ar[maxn];
string s;
vector <pair<int , int>> vec[maxn];

int get(int l , int r)
{
	if(l == 0)  return  prehsh[r];
	int tmp = 1LL * prehsh[l - 1] * pw[r - l + 1] % mod;
	int res = (prehsh[r] + mod - tmp) % mod;
	return res;
}

void Build(int ty , int node = 1 , int nl = 0 , int nr = maxn)
{
	tree[ty][node] = -1;
	if(nl + 1 == nr)  return;
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	Build(ty , lc , nl , mid);  Build(ty , rc , mid , nr);
}

void Add(int ty , int l , int r , int val , int node = 1 , int nl = 0 , int nr = maxn)
{
	if(r <= nl || nr <= l)  return;
	if(l <= nl && nr <= r)
	{
		tree[ty][node] = val;
		return;
	}
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	if(tree[ty][node] != -1)
	{
		tree[ty][lc] = tree[ty][node];
		tree[ty][rc] = tree[ty][node];
		tree[ty][node] = -1;
	}
	Add(ty , l , r , val , lc , nl , mid);  Add(ty , l , r ,val , rc , mid , nr);
}

int Get(int ty , int ind , int node = 1 , int nl = 0 , int nr = maxn)
{
	if(tree[ty][node] != -1)  return  tree[ty][node];
	assert(nl + 1 == nr);
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	if(ind < mid)  return Get(ty , ind , lc , nl , mid);
	else  return Get(ty , ind , rc , mid , nr);
}

int solve(int l , int r)
{
	if(Get(maxl - 1 , l) < r)  return -1;
	int low = 0 , high = (1 << (maxl - 1));
	while(high - low > 1)
	{
		int mid = (high + low) >> 1;
		int tmp = l;
		for(int i = 0 ; i < maxl ; i++)  if((mid >> i) & 1)  tmp = Get(i , tmp);
		if(tmp < r)  low = mid;
		else  high = mid;
	}
	return high;
}

int32_t main()
{
	fast;
	for(int i = 0 ; i < maxl ; i++)  Build(i);
	pw[0] = 1;
	for(int i = 1 ; i < maxn ; i++)  pw[i] = 1LL * pw[i - 1] * Base % mod;

	cin >> n >> m;
	for(int i = 0 ; i < n ; i++)
	{
		string t;  cin >> t;
		int hsh = 0;
		for(int j = 0 ; j < SZ(t) ; j++)
		{
			hsh = 1LL * hsh * Base % mod;
			hsh = (hsh + (t[j] - 'a' + 1)) % mod;
			marked[hsh] = true;
		}
	}
	marked[0] = true;
	cin >> s;
	L = SZ(s);
	for(int i = 0 ; i < m ; i++)  cin >> ar[i].F >> ar[i].S;

	prehsh[0] = s[0] - 'a' + 1;
	for(int i = 1 ; i < L ; i++)
	{
		int now = s[i] - 'a' + 1;
		prehsh[i] = 1LL * prehsh[i - 1] * Base % mod;
		prehsh[i] = (prehsh[i] + now) % mod;
	}
	for(int i = 0 ; i < L ; i++)
	{
		int low = i - 1 , high = L;
		while(high - low > 1)
		{
			int mid = (high + low) >> 1;
			if(marked[get(i , mid)])  low = mid;
			else  high = mid;
		}
		rr[i] = high;
	}
	for(int i = 0 ; i < maxl ; i++)  Add(i , L , L + 1 , L);
	for(int i = 0 ; i < m ; i++)  vec[ar[i].F].pb({i , ar[i].S});

	for(int i = L - 1 ; i > -1 ; i--)
	{
		int low = i , high = L;
		while(high - low > 1)
		{
			int mid = (high + low) >> 1;
			if(Get(0 , mid) < rr[i])
				low = mid;
			else 
				high = mid;
		}
		Add(0 , i , high , rr[i]);
		for(int j = 1 ; j < maxl ; j++)
		{
			int tmp = Get(j - 1 , i);
			tmp = Get(j - 1 , tmp);
			Add(j , i , high , tmp);
		}
		for(auto u : vec[i])
			ans[u.F] = solve(i , u.S);
	}
	for(int i = 0 ; i < m ; i++)  cout << ans[i] << '\n';
	return 0;
}

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