oj.uz

답안 #771016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771016 2023-07-02T10:49:30 Z parsadox2 Dabbeh (INOI20_dabbeh) C++14
0 / 100
 1869 ms 221448 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 , mod = 1e9 + 7 , Base = 727 , maxl = 20;
int n , m , L , pw[maxn] , prehsh[maxn] , tree[maxl][maxn << 2] , rr[maxn] , ans[maxn] , tof[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;
		int tmp = t[0] - 'a' + 1;
		tof[tmp] = 1;
		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 salam = s[i] - 'a' + 1;
		if(tof[salam] != 1)
		{
			rr[i] = i;
			continue;
		}
		int low = i , high = L;
		while(high - low > 1)
		{
			int mid = (high + low) >> 1;
			if(marked[get(i , mid)] && marked[get(i , mid - 1)])  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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 90628 KB Output is correct
2 Correct 392 ms 220628 KB Output is correct
3 Correct 418 ms 220748 KB Output is correct
4 Correct 440 ms 221192 KB Output is correct
5 Correct 448 ms 221448 KB Output is correct
6 Correct 480 ms 221268 KB Output is correct
7 Correct 471 ms 221320 KB Output is correct
8 Incorrect 415 ms 221036 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 90628 KB Output is correct
2 Correct 392 ms 220628 KB Output is correct
3 Correct 418 ms 220748 KB Output is correct
4 Correct 440 ms 221192 KB Output is correct
5 Correct 448 ms 221448 KB Output is correct
6 Correct 480 ms 221268 KB Output is correct
7 Correct 471 ms 221320 KB Output is correct
8 Incorrect 415 ms 221036 KB Output isn't correct
9 Halted 0 ms 0 KB -