oj.uz

Submission #470237

# Submission time Handle Problem Language Result Execution time Memory
470237 2021-09-03T10:00:45 Z AmirrezaM Dabbeh (INOI20_dabbeh) C++14
25 / 100
 1686 ms 457616 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 = 19;
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;
	upd(i);
  }
  lim[l] = l;
  upd(l);
  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) v = par[v];
	if(lim[v] >= r) cout << h[l] - h[v] << endl;
	else cout << -1 << endl;
  }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 27956 KB Output is correct
2 Correct 1581 ms 395588 KB Output is correct
3 Correct 1609 ms 395712 KB Output is correct
4 Correct 1639 ms 395804 KB Output is correct
5 Correct 1642 ms 395972 KB Output is correct
6 Correct 1642 ms 395924 KB Output is correct
7 Correct 1686 ms 395996 KB Output is correct
8 Correct 1675 ms 395784 KB Output is correct
9 Correct 1652 ms 395684 KB Output is correct
10 Correct 1595 ms 377500 KB Output is correct
11 Correct 1628 ms 396088 KB Output is correct
12 Correct 1635 ms 395304 KB Output is correct
13 Correct 1611 ms 395952 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1401 ms 457232 KB Output is correct
2 Incorrect 1421 ms 457616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 27956 KB Output is correct
2 Correct 1581 ms 395588 KB Output is correct
3 Correct 1609 ms 395712 KB Output is correct
4 Correct 1639 ms 395804 KB Output is correct
5 Correct 1642 ms 395972 KB Output is correct
6 Correct 1642 ms 395924 KB Output is correct
7 Correct 1686 ms 395996 KB Output is correct
8 Correct 1675 ms 395784 KB Output is correct
9 Correct 1652 ms 395684 KB Output is correct
10 Correct 1595 ms 377500 KB Output is correct
11 Correct 1628 ms 396088 KB Output is correct
12 Correct 1635 ms 395304 KB Output is correct
13 Correct 1611 ms 395952 KB Output is correct
14 Correct 1401 ms 457232 KB Output is correct
15 Incorrect 1421 ms 457616 KB Output isn't correct
16 Halted 0 ms 0 KB -