Submission #470227

#	Time	Username	Problem	Language	Result	Execution time	Memory
470227		AmirrezaM	Dabbeh (INOI20_dabbeh)	C++17	25 / 100	1324 ms	332892 KiB

Main

#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[2] = {233 , 253} , mod[2] = {1000000007 , 1000000009};

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<1000000020> mark[2];

int pp[2][MAXN] , inv[2][MAXN] , hsh[2][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 < 2 ; 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[2] = {};
	for(int t = 0 ; t < 2 ; 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 < 2 ; 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 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 50