oj.uz

Submission #470235

# Submission time Handle Problem Language Result Execution time Memory
470235 2021-09-03T09:58:24 Z AmirrezaM Dabbeh (INOI20_dabbeh) C++14
25 / 100
 1757 ms 460040 KB 
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define vc vector
#define pb push_back

const int MAXN = 5e5 + 55 , ss = 1 << 19 , lg = 20;
const int p[3] = {233 , 239 , 241} , mod[3] = {1000000007 , 1000000009 , 1000000033};

ll pw(ll a , ll b , int t){
  ll ret = 1;
  while(b){
	if(b&1) ret = (ret * a) % mod[t];
	a = (a * a) % mod[t];
	b >>= 1;
  }
  return ret;
}

int n , q , l;
string s;
bitset<1000000040> mark[3];

int pp[3][MAXN] , inv[3][MAXN] , hsh[3][MAXN];
int get(int l , int r , int t){
  int ret = hsh[t][r];
  if(l){
	ret -= hsh[t][l-1];
	if(ret < 0) ret += mod[t];
  }
  ret = (1ll * ret * inv[t][l]) % mod[t];
  return ret;
}

int lim[MAXN];
int segTree[ss<<1];
int get(int v , int tl , int tr , int l , int r){
  if(l > tr or r < tl or r < l) return -1;
  if(l <= tl and r >= tr) return segTree[v];
  int mid = (tl + tr) >> 1;
  int lf = get(v<<1 , tl , mid , l , r),
	rt = get((v<<1)^1 , mid+1 , tr , l , r);
  int ans = lf;
  if(rt != -1 and (ans == -1 or lim[rt] > lim[ans])) ans = rt;
  return ans;
}
void upd(int id){
  int pos = id + ss;
  while(pos){
	if(segTree[pos] == -1 or lim[id] > lim[segTree[pos]])
	  segTree[pos] = id;
	pos >>= 1;
  }
}

int par[MAXN] , up[MAXN][lg][2] , h[MAXN];
vc<int> adj[MAXN];
void dfs(int v){
  up[v][0][0] = (par[v] == -1 ? v : par[v]);
  up[v][0][1] = lim[v];
  for(int i = 1 ; i < lg ; i++){
	up[v][i][0] = up[up[v][i-1][0]][i-1][0];
	up[v][i][1] = max(up[v][i-1][1] ,
					  up[up[v][i-1][0]][i-1][1]);
  }
  for(int u : adj[v]) h[u] = h[v] + 1 , dfs(u);
}

int main(){
  memset(segTree , -1 , sizeof segTree);
  for(int t = 0 ; t < 3 ; t++){
	pp[t][0] = 1;
	for(int i = 1 ; i < MAXN ; i++) pp[t][i] = (1ll * pp[t][i-1] * p[t]) % mod[t];
	for(int i = 0 ; i < MAXN ; i++) inv[t][i] = pw(pp[t][i] , mod[t]-2 , t);
  }
  cin >> n >> q;
  for(int i = 0 ; i < n ; i++){
	cin >> s;
	int cur[3] = {};
	for(int t = 0 ; t < 3 ; t++){
	  for(int i = 0 ; i < (int)s.size() ; i++){
		cur[t] = (cur[t] + 1ll * s[i] * pp[t][i]) % mod[t];
		mark[t][cur[t]] = 1;
	  }
	}
  }
  cin >> s;
  l = s.size();
  for(int t = 0 ; t < 3 ; t++){
	for(int i = 0 ; i < l ; i++){
	  if(i) hsh[t][i] = hsh[t][i-1];
	  hsh[t][i] = (hsh[t][i] + 1ll * s[i] * pp[t][i]) % mod[t];
	}
  }
  for(int i = 0 ; i < l ; i++){
	int lo = 0 , hi = l - i + 1;
	while(hi - lo > 1){
	  int m = (hi + lo) >> 1;
	  if(mark[0][get(i,i+m-1,0)] and mark[1][get(i,i+m-1,1)]) lo = m;
	  else hi = m;
	}
	lim[i] = i + lo - 1;
	if(lim[i] >= i) upd(i);
  }
  for(int i = 0 ; i < l ; i++){
	par[i] = get(1 , 0 , ss-1 , i+1 , lim[i]+1);
	if(par[i] > -1) adj[par[i]].pb(i);
  }
  for(int i = 0 ; i < l ; i++){
	if(par[i] == -1) dfs(i);
  }
  // for(int i = 0 ; i <= l ; i++){
  // 	cout << i << " " << lim[i] << " " << par[i] << " : " << endl;
  // 	for(int j = 0 ; j < lg ; j++) cout << up[i][j][0] << " ";
  // 	cout << endl;
  // 	for(int j = 0 ; j < lg ; j++) cout << up[i][j][1] << " ";
  // 	cout << endl;
  // }
  while(q--){
	int l , r;
	cin >> l >> r;
	r--;
	int v = l;
	for(int i = lg-1 ; i >= 0 ; i--){
	  if(up[v][i][1] < r) v = up[v][i][0];
	}
	if(v != -1 and lim[v] >= r) cout << h[l] - h[v] + 1 << endl;
	else cout << -1 << endl;
  }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 27992 KB Output is correct
2 Correct 1618 ms 395588 KB Output is correct
3 Correct 1601 ms 395768 KB Output is correct
4 Correct 1626 ms 395760 KB Output is correct
5 Correct 1634 ms 395884 KB Output is correct
6 Correct 1660 ms 395844 KB Output is correct
7 Correct 1757 ms 396004 KB Output is correct
8 Correct 1638 ms 395748 KB Output is correct
9 Correct 1681 ms 395700 KB Output is correct
10 Correct 1579 ms 377108 KB Output is correct
11 Correct 1604 ms 396036 KB Output is correct
12 Correct 1606 ms 395432 KB Output is correct
13 Correct 1582 ms 395924 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1417 ms 459468 KB Output is correct
2 Incorrect 1400 ms 460040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 27992 KB Output is correct
2 Correct 1618 ms 395588 KB Output is correct
3 Correct 1601 ms 395768 KB Output is correct
4 Correct 1626 ms 395760 KB Output is correct
5 Correct 1634 ms 395884 KB Output is correct
6 Correct 1660 ms 395844 KB Output is correct
7 Correct 1757 ms 396004 KB Output is correct
8 Correct 1638 ms 395748 KB Output is correct
9 Correct 1681 ms 395700 KB Output is correct
10 Correct 1579 ms 377108 KB Output is correct
11 Correct 1604 ms 396036 KB Output is correct
12 Correct 1606 ms 395432 KB Output is correct
13 Correct 1582 ms 395924 KB Output is correct
14 Correct 1417 ms 459468 KB Output is correct
15 Incorrect 1400 ms 460040 KB Output isn't correct
16 Halted 0 ms 0 KB -