oj.uz

Submission #470233

# Submission time Handle Problem Language Result Execution time Memory
470233 2021-09-03T09:57:18 Z AmirrezaM Dabbeh (INOI20_dabbeh) C++14
25 / 100
 1619 ms 459800 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 , 253 , 239} , 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 760 ms 27940 KB Output is correct
2 Correct 1614 ms 395636 KB Output is correct
3 Correct 1581 ms 395808 KB Output is correct
4 Correct 1594 ms 395820 KB Output is correct
5 Correct 1588 ms 395848 KB Output is correct
6 Correct 1619 ms 395852 KB Output is correct
7 Correct 1613 ms 395988 KB Output is correct
8 Correct 1617 ms 395840 KB Output is correct
9 Correct 1609 ms 395696 KB Output is correct
10 Correct 1590 ms 377500 KB Output is correct
11 Correct 1610 ms 396124 KB Output is correct
12 Correct 1581 ms 395432 KB Output is correct
13 Correct 1589 ms 396212 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1382 ms 459552 KB Output is correct
2 Incorrect 1423 ms 459800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 27940 KB Output is correct
2 Correct 1614 ms 395636 KB Output is correct
3 Correct 1581 ms 395808 KB Output is correct
4 Correct 1594 ms 395820 KB Output is correct
5 Correct 1588 ms 395848 KB Output is correct
6 Correct 1619 ms 395852 KB Output is correct
7 Correct 1613 ms 395988 KB Output is correct
8 Correct 1617 ms 395840 KB Output is correct
9 Correct 1609 ms 395696 KB Output is correct
10 Correct 1590 ms 377500 KB Output is correct
11 Correct 1610 ms 396124 KB Output is correct
12 Correct 1581 ms 395432 KB Output is correct
13 Correct 1589 ms 396212 KB Output is correct
14 Correct 1382 ms 459552 KB Output is correct
15 Incorrect 1423 ms 459800 KB Output isn't correct
16 Halted 0 ms 0 KB -