oj.uz

Submission #470148

# Submission time Handle Problem Language Result Execution time Memory
470148 2021-09-03T06:38:08 Z AmirrezaM Dabbeh (INOI20_dabbeh) C++17
0 / 100
 2000 ms 102556 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 = 3e5 + 35 , ss = 1 << 19 , lg = 20 , p = 233 , mod = 1e9 + 7;

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

int n , q , l;
string s;
map<int,int> mark;

int pp[MAXN] , inv[MAXN] , hsh[MAXN];
int get(int l , int r){
  int ret = hsh[r];
  if(l){
	ret -= hsh[l-1];
	if(ret < 0) ret += mod;
  }
  ret = (1ll * ret * inv[l]) % mod;
  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) / 2;
  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);
  pp[0] = 1;
  for(int i = 1 ; i < MAXN ; i++) pp[i] = (1ll * pp[i-1] * p) % mod;
  for(int i = 0 ; i < MAXN ; i++) inv[i] = pw(pp[i] , mod-2);
  cin >> n >> q;
  for(int i = 0 ; i < n ; i++){
	cin >> s;
	int cur = 0;
	for(int i = 0 ; i < (int)s.size() ; i++){
	  cur = (cur + 1ll * s[i] * pp[i]) % mod;
	  mark[cur] = 1;
	}
  }
  cin >> s;
  l = s.size();
  for(int i = 0 ; i < l ; i++){
	if(i) hsh[i] = hsh[i-1];
	hsh[i] = (hsh[i] + 1ll * s[i] * pp[i]) % mod;
  }
  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[get(i,i+m-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 and lim[v] >= r) cout << h[l] - h[v] + 1 << endl;
	else cout << -1 << endl;
  }
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13764 KB Output is correct
2 Correct 936 ms 32208 KB Output is correct
3 Correct 879 ms 27428 KB Output is correct
4 Incorrect 1059 ms 31828 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2101 ms 102556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13764 KB Output is correct
2 Correct 936 ms 32208 KB Output is correct
3 Correct 879 ms 27428 KB Output is correct
4 Incorrect 1059 ms 31828 KB Output isn't correct
5 Halted 0 ms 0 KB -