| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 634882 |
2022-08-25T08:05:31 Z |
S2speed |
Dabbeh (INOI20_dabbeh) |
C++17 |
|
672 ms |
128884 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;
typedef pair<int , int> pii;
const ll maxn = 9e5 + 17 , md = 2000000357 , P = 131 , inf = 2e16;
pii val[maxn];
struct segtree {
int sz = 1;
void init(int n){
while(sz < n) sz <<= 1;
fill(val , val + (sz << 1) , make_pair(-1 , -1));
return;
}
void build(vector<pii> &a , int x , int lx , int rx){
if(rx - lx == 1){
if(lx < sze(a)){
val[x] = a[lx];
}
return;
}
int 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<pii> &a){
build(a , 0 , 0 , sz);
return;
}
pii cal(int l , int r , int x , int lx , int rx){
if(rx <= l || lx >= r) return {-1 , -1};
if(rx <= r && lx >= l) return val[x];
int m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
pii a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
return max(a , b);
}
pii cal(int l , int r){
return cal(l , r , 0 , 0 , sz);
}
};
segtree st;
int k , q , n , m;
ll tv[maxn] , hs[maxn];
string t[maxn] , s;
int r[maxn] , rnk[maxn] , sf[maxn] , pn[maxn] , cnt[maxn] , x[maxn] , y[maxn] , l[maxn];
int mx[maxn] , f[maxn] , jad[maxn][20];
vector<int> imp;
int v[maxn];
vector<pii> a;
ll get_hs(int l , int 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;
}
int lcp(int i , int j){
int l = 0 , r = n;
while(l < r - 1){
int 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(int i = 1 ; i < maxn ; i++){
tv[i] = tv[i - 1] * P % md;
}
cin>>k>>q;
for(int i = 0 ; i < k ; i++){
cin>>t[i];
}
cin>>s; m = sze(s);
s += '$';
for(int i = 0 ; i < k ; i++){
s += t[i]; s += '$';
}
n = sze(s);
hs[0] = s[0];
for(int i = 1 ; i < n ; i++){
hs[i] = (hs[i - 1] * P + s[i]) % md;
}
int lm = max(n , 131);
for(int i = 0 ; i < n ; i++){
cnt[s[i]]++;
}
int cur = 0 , o = 0;
for(int i = 0 ; i < 131 ; i++){
x[i] = cur;
cur += cnt[i];
if(cnt[i] > 0){
y[i] = o++;
}
}
for(int i = 0 ; i < n ; i++){
sf[x[s[i]]++] = i;
r[i] = y[s[i]];
}
for(int z = 1 ; z < n ; z <<= 1){
for(int i = 0 ; i < n ; i++){
pn[i] = (sf[i] - z < 0 ? sf[i] - z + n : sf[i] - z);
}
memset(cnt , 0 , 4 * o);
for(int i = 0 ; i < n ; i++){
cnt[r[sf[i]]]++;
}
for(int i = 1 ; i < o ; i++){
cnt[i] += cnt[i - 1];
}
for(int i = n - 1 ; ~i ; i--){
sf[--cnt[r[pn[i]]]] = pn[i];
}
rnk[sf[0]] = 0;
o = 0;
for(int i = 1 ; i < n ; i++){
pii a = {r[sf[i]] , (sf[i] + z >= n ? r[sf[i] + z - n] : r[sf[i] + z])};
pii b = {r[sf[i - 1]] , (sf[i - 1] + z >= n ? r[sf[i - 1] + z - n] : r[sf[i - 1] + z])};
o += (a != b);
rnk[sf[i]] = o;
}
o++;
memcpy(r , rnk , 4 * n);
}
// for(int i = 0 ; i < n ; i++){
// cout<<sf[i]<<' ';
// }
// cout<<'\n';
for(int i = 0 ; i < n ; i++){
if(sf[i] < m){
imp.push_back(i);
} else if(s[sf[i] - 1] == '$'){
imp.push_back(i);
}
}
// for(int i = 0 ; i < n ; i++){
// cout<<sf[i]<<' ';
// }
// cout<<'\n';
int sz = sze(imp);
for(int i = 0 ; i < sz - 1 ; i++){
l[i] = lcp(sf[imp[i]] , sf[imp[i + 1]]);
// cout<<l[i]<<' ';
}
// cout<<'\n';
int t = -1;
for(int j = 0 ; j < sz ; j++){
int i = imp[j];
if(sf[i] < m){
mx[sf[i]] = t;
} else {
t = n - sf[i];
}
t = min(t , l[j]);
}
t = -1;
for(int j = sz - 1 ; ~j ; j--){
int i = imp[j];
t = min(t , l[j]);
if(sf[i] < m){
mx[sf[i]] = max(mx[sf[i]] , t);
} else {
t = n - sf[i];
}
}
for(int 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(int i = m - 1 ; ~i ; i--){
pii p = st.cal(i + 1 , f[i] + 1);
if(p.first <= f[i]){
for(int j = 0 ; j < 20 ; j++){
jad[i][j] = i;
}
continue;
}
jad[i][0] = p.second;
for(int j = 1 ; j < 20 ; j++){
jad[i][j] = jad[jad[i][j - 1]][j - 1];
}
}
for(int i = 0 ; i < m ; i++){
// cout<<jad[i][0]<<' ';
}
// cout<<'\n';
for(int e = 0 ; e < q ; e++){
int l , r;
cin>>l>>r;
if(f[jad[l][19]] < r){
cout<<"-1\n";
continue;
}
if(f[l] >= r){
cout<<"1\n";
continue;
}
int v = l , res = 2;
for(int j = 19 ; ~j ; j--){
int u = jad[v][j];
if(f[u] >= r) continue;
v = u; res += (1 << j);
}
cout<<res<<'\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:114:11: warning: array subscript has type 'char' [-Wchar-subscripts]
114 | cnt[s[i]]++;
| ^
Main.cpp:125:12: warning: array subscript has type 'char' [-Wchar-subscripts]
125 | sf[x[s[i]]++] = i;
| ^
Main.cpp:126:16: warning: array subscript has type 'char' [-Wchar-subscripts]
126 | r[i] = y[s[i]];
| ^
Main.cpp:112:6: warning: unused variable 'lm' [-Wunused-variable]
112 | int lm = max(n , 131);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
35540 KB |
Output is correct |
| 2 |
Correct |
447 ms |
47996 KB |
Output is correct |
| 3 |
Correct |
311 ms |
44884 KB |
Output is correct |
| 4 |
Correct |
508 ms |
48396 KB |
Output is correct |
| 5 |
Correct |
416 ms |
46684 KB |
Output is correct |
| 6 |
Correct |
602 ms |
50416 KB |
Output is correct |
| 7 |
Correct |
672 ms |
50856 KB |
Output is correct |
| 8 |
Correct |
647 ms |
51252 KB |
Output is correct |
| 9 |
Correct |
518 ms |
49100 KB |
Output is correct |
| 10 |
Correct |
151 ms |
39908 KB |
Output is correct |
| 11 |
Correct |
196 ms |
48468 KB |
Output is correct |
| 12 |
Correct |
124 ms |
42140 KB |
Output is correct |
| 13 |
Correct |
162 ms |
45840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
640 ms |
128884 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
35540 KB |
Output is correct |
| 2 |
Correct |
447 ms |
47996 KB |
Output is correct |
| 3 |
Correct |
311 ms |
44884 KB |
Output is correct |
| 4 |
Correct |
508 ms |
48396 KB |
Output is correct |
| 5 |
Correct |
416 ms |
46684 KB |
Output is correct |
| 6 |
Correct |
602 ms |
50416 KB |
Output is correct |
| 7 |
Correct |
672 ms |
50856 KB |
Output is correct |
| 8 |
Correct |
647 ms |
51252 KB |
Output is correct |
| 9 |
Correct |
518 ms |
49100 KB |
Output is correct |
| 10 |
Correct |
151 ms |
39908 KB |
Output is correct |
| 11 |
Correct |
196 ms |
48468 KB |
Output is correct |
| 12 |
Correct |
124 ms |
42140 KB |
Output is correct |
| 13 |
Correct |
162 ms |
45840 KB |
Output is correct |
| 14 |
Runtime error |
640 ms |
128884 KB |
Execution killed with signal 11 |
| 15 |
Halted |
0 ms |
0 KB |
- |
