| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 992010 |
2024-06-03T14:31:11 Z |
saddd |
Dabbeh (INOI20_dabbeh) |
C++17 |
|
298 ms |
55248 KB |
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
//#pragma GCC optimize("O3")
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
ll mod = 998244353, pr = 69;
const int mxn = 3e5 + 5, mxq = 1e5 + 5, sq = 1005, mxv = 5e4 + 1, lg = 60;
//const int base = (1 <<18);
const ll inf = 2e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rr(ll l, ll r){
return(uniform_int_distribution<ll>(l, r)(rng));
}
// have fun!
struct Hash{
vt<ll>hsh, pw;
void init(string s){
pw.resize(sz(s) + 1, 0); hsh.resize(sz(s) + 1, 0);
for(int i = 0; i < sz(s); i++){
hsh[i + 1] = (hsh[i] * pr + (s[i] - 'a' + 1)) % mod;
}
pw[0] = 1;
for(int i = 1; i <= sz(s); i++){
pw[i] = (pw[i - 1] * pr) % mod;
}
}
ll get(int l, int r){
return((hsh[r + 1] - hsh[l] * pw[r - l + 1] + mod * mod) % mod);
}
};
Hash ht[mxn + 1], hs;
int n, m;
string t[mxn + 1], s;
pii get(int ids, int idt){
int l = 1, r = min(sz(s) - ids, sz(t[idt])), ans = 0;
while(l <= r){
int mid = (l + r) >> 1;
if(hs.get(ids, ids + mid - 1) == ht[idt].hsh[mid]){
ans = mid; l = mid + 1;
}else{
r = mid - 1;
}
}
if(ans == min(sz(s) - ids, sz(t[idt]))){
return(mpp(ans, sz(s) - ids < sz(t[idt])));
}else{
return(mpp(ans, s[ids + ans] < t[idt][ans]));
}
}
int up[mxn + 1][19];
void solve(){
cin >> n >> m;
mod = rr(1e8, 1e9);
for(int i = 1; i <= n; i++){
cin >> t[i];
}
sort(t + 1, t + n + 1);
for(int i = 1; i <= n; i++)ht[i].init(t[i]);
cin >> s; hs.init(s);
for(int i = 0; i < sz(s); i++){
int l = 1, r = n, ans = 0;
while(l <= r){
int mid = (l + r) >> 1;
pii cand = get(i, mid);
ans = max(ans, cand.fi);
if(cand.se == 0){
l = mid + 1;
}else{
r = mid - 1;
}
}
up[i][0] = i + ans;
}
up[sz(s)][0] = sz(s);
for(int i = 1; i < 19; i++){
deque<int>dq;
for(int j = sz(s); j >= 0; j--){
while(sz(dq) && up[j][i - 1] >= up[dq.back()][i - 1])dq.pop_back();
dq.pb(j);
int l = 0, r = sz(dq) - 1, ans;
while(l <= r){
int mid = (l + r) >> 1;
if(dq[mid] <= up[j][i - 1]){
ans = mid; r = mid - 1;
}else{
l = mid + 1;
}
}
up[j][i] = up[dq[ans]][i - 1];
}
}
while(m--){
int l, r; cin >> l >> r; r--;
int ans = 0;
for(int i = 18; i >= 0; i--){
if(up[l][i] <= r){
ans += (1 << i); l = up[l][i];
}
}
cout << ((ans == ((1 << 19) - 1)) ? -1 : ans + 1) << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("TESTROOMS.inp", "r", stdin);
//freopen("TESTROOMS.out", "w", stdout);
int tt; tt = 1;
while(tt--){
solve();
}
return(0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
25436 KB |
Output is correct |
| 2 |
Correct |
61 ms |
32940 KB |
Output is correct |
| 3 |
Incorrect |
62 ms |
31036 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
298 ms |
55248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
25436 KB |
Output is correct |
| 2 |
Correct |
61 ms |
32940 KB |
Output is correct |
| 3 |
Incorrect |
62 ms |
31036 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
