#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define lc 2 * v
#define rc 2 * v + 1
#define mid (s + e) / 2
#define PB push_back
#define ll long long
#define ld long double
#define _sz(e) (int)e.size()
#define pii pair <int , int>
#define _all(e) e.begin() , e.end()
#define FAST ios::sync_with_stdio(0); cin.tie(0);
#pragma GCC target("sse,avx,avx2")
#pragma GCC optimize("O3,unroll-loops")
const ll maxn = 3e5 + 4 , N = 1e4 + 4 , base = 307 , mod = 1e9 + 7 , INF = 1e9 , lg = 19;
struct node {
int mx[lg];
};
node seg[4 * maxn];
string t[N];
ll pbase[maxn];
vector <ll> h[N];
int n , m , ql[maxn] , qr[maxn] , SZ , dp[lg][maxn];
void pre() {
pbase[0] = 1;
for (int i = 1; i < maxn; ++i) {
pbase[i] = (pbase[i - 1] * base) % mod;
}
for (int i = 0; i <= n; ++i) {
h[i].PB(0);
for (int j = 1; j <= _sz(t[i]); ++j) {
int val = (h[i].back() * base + t[i][j - 1]) % mod;
h[i].PB(val);
}
}
}
inline int HASH(int i , int l , int r) {
return (h[i][r] - (h[i][l] * pbase[r - l] % mod) + mod) % mod;
}
inline int LCP(int x , int i) {
if(t[0][x] != t[i][0]) return 0;
int l = 1 , r = min(SZ - x , _sz(t[i])) + 1;
while(l < r - 1) {
int mm = (l + r) / 2;
if(HASH(0 , x , x + mm) == HASH(i , 0 , mm)) l = mm;
else r = mm;
}
return l;
}
inline bool check(int x , int i) {
int lcp = LCP(x , i);
if(x + lcp == SZ) return (_sz(t[i]) > lcp);
if(_sz(t[i]) == lcp) return 0;
return t[0][x + lcp] < t[i][lcp];
}
inline int bs(int x) {
if(check(x , 1)) return 1;
int l = 1 , r = n + 1;
while(l < r - 1) {
int mm = (l + r) / 2;
if(check(x , mm)) r = mm;
else l = mm;
}
return r;
}
void add(int i , int p , int x , int v = 1 , int s = 0 , int e = SZ) {
seg[v].mx[i] = max(seg[v].mx[i] , x);
if(e - s == 1) return ;
if(p < mid) {
add(i , p , x , lc , s , mid);
return ;
}
add(i , p , x , rc , mid , e);
}
int get(int i , int l , int r , int v = 1 , int s = 0 , int e = SZ) {
if(l >= e || s >= r) return 0;
if(l <= s && e <= r) return seg[v].mx[i];
return max(get(i , l , r , lc , s , mid) , get(i , l , r , rc , mid , e));
}
int main() {
FAST;
freopen("2-01.in" , "r" , stdin);
freopen("2-01.out" , "w" , stdout);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> t[i];
}
cin >> t[0];
sort(t + 1 , t + 1 + n);
for (int i = 0; i < m; ++i) {
cin >> ql[i] >> qr[i];
}
pre();
SZ = _sz(t[0]);
for (int i = 0; i < SZ; ++i) {
int p = bs(i);
if(p <= n) dp[0][i] = max(dp[0][i] , i + LCP(i , p));
if(p > 0) dp[0][i] = max(dp[0][i] , i + LCP(i , p - 1));
add(0 , i , dp[0][i]);
}
for (int i = 1; i < lg; ++i) {
for (int j = 0; j < SZ; ++j) {
dp[i][j] = get(i - 1 , j , dp[i - 1][j] + 1);
add(i , j , dp[i][j]);
}
}
for (int i = 0; i < m; ++i) {
int cost = 0 , mx = ql[i];
for (int j = lg - 1; j >= 0; --j) {
int idx = get(j , ql[i] , mx + 1);
if(idx >= qr[i]) continue;
cost += (1 << j) , mx = idx;
}
cout << (get(0 , ql[i] , mx + 1) >= qr[i] ? cost + 1 : -1) << '\n';
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:98:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | freopen("2-01.in" , "r" , stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:99:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | freopen("2-01.out" , "w" , stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
