oj.uz

답안 #771013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771013 2023-07-02T10:43:13 Z parsadox2 Dabbeh (INOI20_dabbeh) C++14
25 / 100
 1887 ms 224128 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 = 131 , 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
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 90664 KB Output is correct
2 Correct 382 ms 220644 KB Output is correct
3 Correct 400 ms 220772 KB Output is correct
4 Correct 411 ms 223820 KB Output is correct
5 Correct 485 ms 223968 KB Output is correct
6 Correct 416 ms 223916 KB Output is correct
7 Correct 458 ms 224128 KB Output is correct
8 Correct 396 ms 223748 KB Output is correct
9 Correct 438 ms 223748 KB Output is correct
10 Correct 358 ms 217368 KB Output is correct
11 Correct 350 ms 223564 KB Output is correct
12 Correct 321 ms 223088 KB Output is correct
13 Correct 350 ms 223356 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 90664 KB Output is correct
2 Correct 382 ms 220644 KB Output is correct
3 Correct 400 ms 220772 KB Output is correct
4 Correct 411 ms 223820 KB Output is correct
5 Correct 485 ms 223968 KB Output is correct
6 Correct 416 ms 223916 KB Output is correct
7 Correct 458 ms 224128 KB Output is correct
8 Correct 396 ms 223748 KB Output is correct
9 Correct 438 ms 223748 KB Output is correct
10 Correct 358 ms 217368 KB Output is correct
11 Correct 350 ms 223564 KB Output is correct
12 Correct 321 ms 223088 KB Output is correct
13 Correct 350 ms 223356 KB Output is correct
14 Incorrect 1887 ms 215100 KB Output isn't correct
15 Halted 0 ms 0 KB -