Submission #771042

#	Time	Username	Problem	Language	Result	Execution time	Memory
771042		parsadox2	Dabbeh (INOI20_dabbeh)	C++14	0 / 100	2085 ms	102492 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 , mod2 = 2000000357;
int n , m , L , pw[2][maxn] , prehsh[2][maxn] , tree[maxl][maxn << 2] , rr[maxn] , ans[maxn];
pair<int , int> ar[maxn];
string s;
vector <pair<int , int>> vec[maxn] , allh;

inline int modit(int a , int mm)
{
	if(a >= mm)  a -= mm;
	return a;
}

inline pair<int , int> get(int l , int r)
{
	if(l == 0)  return make_pair(prehsh[0][r] , prehsh[1][r]);
	int tmp = 1LL * prehsh[0][l - 1] * pw[0][r - l + 1] % mod;
	int res = modit(prehsh[0][r] + mod - tmp , mod);
	int tmp2 = 1LL * prehsh[1][l - 1] * pw[0][r - l + 1] % mod2;
	int res2 = modit(prehsh[1][r] + mod2 - tmp2 , mod2);
	return make_pair(res , res2);
}

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);
}

inline 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][0] = 1;
	for(int i = 1 ; i < maxn ; i++)  pw[0][i] = 1LL * pw[0][i - 1] * Base % mod;
	pw[1][0] = 1;
	for(int i = 1 ; i < maxn ; i++)  pw[1][i] = 1LL * pw[1][i - 1] * Base % mod2;

	cin >> n >> m;
	for(int i = 0 ; i < n ; i++)
	{
		string t;  cin >> t;
		int hsh0 = 0 , hsh1 = 0;
		for(int j = 0 ; j < SZ(t) ; j++)
		{
			hsh0 = 1LL * hsh0 * Base % mod;
			hsh0 = modit(hsh0 + (t[j] - 'a' + 1) , mod);
			hsh1 = 1LL * hsh1 * Base % mod2;
			hsh1 = modit(hsh1 + (t[j] - 'a' + 1) , mod2);
			allh.pb({hsh0 , hsh1});
		}
	}
	allh.pb({0 , 0});
	sort(allh.begin() , allh.end());
	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] - 'a' + 1;
	for(int i = 1 ; i < L ; i++)
	{
		int now = s[i] - 'a' + 1;
		prehsh[0][i] = 1LL * prehsh[0][i - 1] * Base % mod;
		prehsh[0][i] = modit(prehsh[0][i] + now , mod);
		prehsh[1][i] = 1LL * prehsh[1][i - 1] * Base % mod2;
		prehsh[1][i] = modit(prehsh[1][i] + now , mod2);
	}
	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 pos1 = lower_bound(allh.begin() , allh.end() , now) - allh.begin();
			int pos2 = upper_bound(allh.begin() , allh.end() , now) - allh.begin();
			if(pos1 != pos2)  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