| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 634232 |
2022-08-24T07:31:49 Z |
S2speed |
Dabbeh (INOI20_dabbeh) |
C++17 |
|
2000 ms |
104872 KB |
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
const ll maxn = 9e5 + 17 , md = 2000000357 , P = 131 , inf = 2e16;
struct segtree {
ll sz = 1;
vector<pll> val;
void init(ll n){
while(sz < n) sz <<= 1;
val.assign(sz << 1 , {-1 , -1});
return;
}
void build(vector<pll> &a , ll x , ll lx , ll rx){
if(rx - lx == 1){
if(lx < sze(a)){
val[x] = a[lx];
}
return;
}
ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
build(a , ln , lx , m); build(a , rn , m , rx);
val[x] = max(val[ln] , val[rn]);
return;
}
void build(vector<pll> &a){
build(a , 0 , 0 , sz);
return;
}
pll cal(ll l , ll r , ll x , ll lx , ll rx){
if(rx <= l || lx >= r) return {-1 , -1};
if(rx <= r && lx >= l) return val[x];
ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
pll a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
return max(a , b);
}
pll cal(ll l , ll r){
return cal(l , r , 0 , 0 , sz);
}
};
segtree st;
ll k , q , n , m;
ll tv[maxn];
string t[maxn] , s;
ll r[maxn] , rnk[maxn] , sf[maxn] , hs[maxn] , l[maxn];
ll mx[maxn] , f[maxn] , jad[maxn][20];
vector<ll> cnt[maxn] , v;
vector<pll> a;
ll get_hs(ll l , ll r){
if(r > n) return -inf - l;
ll res = hs[r - 1];
if(l){
res -= hs[l - 1] * tv[r - l];
res %= md; res += (res < 0) * md;
}
return res;
}
ll lcp(ll i , ll j){
ll l = 0 , r = n;
while(l < r - 1){
ll m = (r + l) >> 1;
if(get_hs(i , i + m) == get_hs(j , j + m)){
l = m;
} else {
r = m;
}
}
return l;
}
int main(){
ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
tv[0] = 1;
for(ll i = 1 ; i < maxn ; i++){
tv[i] = tv[i - 1] * P % md;
}
cin>>k>>q;
for(ll i = 0 ; i < k ; i++){
cin>>t[i];
}
cin>>s; m = sze(s);
s += '{';
for(ll i = 0 ; i < k ; i++){
s += t[i]; s += '{';
}
n = sze(s);
hs[0] = s[0];
for(ll i = 1 ; i < n ; i++){
hs[i] = (hs[i - 1] * P + s[i]) % md;
}
ll lm = max(n , 131ll);
for(ll i = 0 ; i < n ; i++){
r[i] = s[i];
}
for(ll z = 1 ; z < n ; z <<= 1){
for(ll i = 0 ; i + z < n ; i++){
rnk[i] = r[i + z];
}
for(ll i = n - z ; i < n ; i++){
rnk[i] = 0;
}
for(ll i = 0 ; i <= lm ; i++) cnt[i].clear();
v.clear();
for(ll i = 0 ; i < n ; i++){
cnt[rnk[i]].push_back(i);
}
for(ll i = 0 ; i <= lm ; i++){
for(auto j : cnt[i]) v.push_back(j);
}
for(ll i = 0 ; i <= lm ; i++) cnt[i].clear();
for(auto i : v){
cnt[r[i]].push_back(i);
}
ll o = 0;
for(ll i = 0 ; i <= lm ; i++){
if(cnt[i].empty()) continue;
r[cnt[i][0]] = ++o;
ll cs = sze(cnt[i]);
for(ll e = 1 ; e < cs ; e++){
ll j = cnt[i][e] , pr = cnt[i][e - 1];
if(rnk[j] == rnk[pr]){
r[j] = o;
} else {
r[j] = ++o;
}
}
}
}
for(ll i = 0 ; i < n ; i++){
sf[r[i] - 1] = i;
}
// for(ll i = 0 ; i < n ; i++){
// cout<<sf[i]<<' ';
// }
// cout<<'\n';
for(ll i = 0 ; i < n - 1 ; i++){
l[i] = lcp(sf[i] , sf[i + 1]);
// cout<<l[i]<<' ';
}
// cout<<'\n';
ll t = -1;
for(ll i = 0 ; i < n ; i++){
if(sf[i] < m){
mx[sf[i]] = t;
} else if(s[sf[i] - 1] == '{'){
t = n - sf[i];
}
t = min(t , l[i]);
}
t = -1;
for(ll i = n - 1 ; ~i ; i--){
t = min(t , l[i]);
if(sf[i] < m){
mx[sf[i]] = max(mx[sf[i]] , t);
} else if(s[sf[i] - 1] == '{'){
t = n - sf[i];
}
}
for(ll i = 0 ; i < m ; i++){
f[i] = min(m , i + mx[i]);
// cout<<f[i]<<' ';
a.push_back({f[i] , i});
}
// cout<<'\n';
st.init(m);
st.build(a);
for(ll i = m - 1 ; ~i ; i--){
pll p = st.cal(i + 1 , f[i] + 1);
if(p.first <= f[i]){
for(ll j = 0 ; j < 20 ; j++){
jad[i][j] = i;
}
continue;
}
jad[i][0] = p.second;
for(ll j = 1 ; j < 20 ; j++){
jad[i][j] = jad[jad[i][j - 1]][j - 1];
}
}
for(ll i = 0 ; i < m ; i++){
// cout<<jad[i][0]<<' ';
}
// cout<<'\n';
for(ll e = 0 ; e < q ; e++){
ll l , r;
cin>>l>>r;
if(f[jad[l][19]] < r){
cout<<"-1\n";
continue;
}
if(f[l] >= r){
cout<<"1\n";
continue;
}
ll v = l , res = 2;
for(ll j = 19 ; ~j ; j--){
ll u = jad[v][j];
if(f[u] >= r) continue;
v = u; res += (1 << j);
}
cout<<res<<'\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
56680 KB |
Output is correct |
| 2 |
Correct |
1581 ms |
103976 KB |
Output is correct |
| 3 |
Correct |
1230 ms |
92308 KB |
Output is correct |
| 4 |
Execution timed out |
2078 ms |
104872 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2087 ms |
102764 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
56680 KB |
Output is correct |
| 2 |
Correct |
1581 ms |
103976 KB |
Output is correct |
| 3 |
Correct |
1230 ms |
92308 KB |
Output is correct |
| 4 |
Execution timed out |
2078 ms |
104872 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
