oj.uz

Submission #470231

# Submission time Handle Problem Language Result Execution time Memory
470231 2021-09-03T09:55:45 Z AmirrezaM Dabbeh (INOI20_dabbeh) C++17
25 / 100
 1454 ms 337944 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} , 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 616 ms 28336 KB Output is correct
2 Correct 1371 ms 273380 KB Output is correct
3 Correct 1401 ms 273504 KB Output is correct
4 Correct 1411 ms 273764 KB Output is correct
5 Correct 1409 ms 273532 KB Output is correct
6 Correct 1419 ms 273628 KB Output is correct
7 Correct 1406 ms 273796 KB Output is correct
8 Correct 1454 ms 273652 KB Output is correct
9 Correct 1422 ms 273492 KB Output is correct
10 Correct 1377 ms 261032 KB Output is correct
11 Correct 1392 ms 273744 KB Output is correct
12 Correct 1415 ms 273236 KB Output is correct
13 Correct 1386 ms 273628 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 337944 KB Output is correct
2 Incorrect 1182 ms 337552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 28336 KB Output is correct
2 Correct 1371 ms 273380 KB Output is correct
3 Correct 1401 ms 273504 KB Output is correct
4 Correct 1411 ms 273764 KB Output is correct
5 Correct 1409 ms 273532 KB Output is correct
6 Correct 1419 ms 273628 KB Output is correct
7 Correct 1406 ms 273796 KB Output is correct
8 Correct 1454 ms 273652 KB Output is correct
9 Correct 1422 ms 273492 KB Output is correct
10 Correct 1377 ms 261032 KB Output is correct
11 Correct 1392 ms 273744 KB Output is correct
12 Correct 1415 ms 273236 KB Output is correct
13 Correct 1386 ms 273628 KB Output is correct
14 Correct 1183 ms 337944 KB Output is correct
15 Incorrect 1182 ms 337552 KB Output isn't correct
16 Halted 0 ms 0 KB -