oj.uz

Submission #470201

# Submission time Handle Problem Language Result Execution time Memory
470201 2021-09-03T08:55:34 Z AmirrezaM Dabbeh (INOI20_dabbeh) C++14
0 / 100
 2000 ms 95476 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 mod;
  if(l <= tl and r >= tr) return segTree[v];
  int mid = (tl + tr) >> 1;
  return min(get(v<<1 , tl , mid , l , r),
			 get((v<<1)^1 , mid+1 , tr , l , r));
}
void upd(int id , int x){
  int pos = id + ss;
  segTree[pos] = x;
  pos >>= 1;
  while(pos){
	segTree[pos] = min(segTree[pos<<1] , segTree[(pos<<1)^1]);
	pos >>= 1;
  }
}

int main(){
  for(int i = 0 ; i < (ss << 1) ; i++) segTree[i] = mod;
  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;
  }
  
  map<pii , int> ans;
  while(q--){
	int l , r;
	cin >> l >> r;
	r--;
	if(ans[{l,r}]){
	  cout << ans[{l,r}] << endl;
	  continue;
	}
	upd(r+1 , 0);
	int dp = 0;
	for(int i = r ; i >= l ; i--){
	  dp = get(1 , 0 , ss-1 , i+1 , lim[i]+1) + 1;
	  upd(i , dp);
	}
	for(int i = l ; i <= r ; i++){
	  upd(i , mod);
	}
	if(dp > MAXN) dp = -1;
	ans[{l,r}] = dp;
	cout << dp << endl;
  }
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 6724 KB Output is correct
2 Correct 1051 ms 25796 KB Output is correct
3 Execution timed out 2077 ms 23100 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 6724 KB Output is correct
2 Correct 1051 ms 25796 KB Output is correct
3 Execution timed out 2077 ms 23100 KB Time limit exceeded
4 Halted 0 ms 0 KB -