| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 771020 |
2023-07-02T10:53:43 Z |
parsadox2 |
Dabbeh (INOI20_dabbeh) |
C++14 |
|
2000 ms |
197096 KB |
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define debug(x) cout << #x << "= " << x << ", "
#define ll long long
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define SZ(x) (int) x.size()
#define wall cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 3e5 + 10 , mod = 2000000357 , Base = 131 , maxl = 20;
int n , m , L , pw[maxn] , prehsh[maxn] , tree[maxl][maxn << 2] , rr[maxn] , ans[maxn] , tof[maxn];
map <int , int> marked;
pair<int , int> ar[maxn];
string s;
vector <pair<int , int>> vec[maxn];
int modit(int a)
{
if(a >= mod) a -= mod;
return a;
}
int get(int l , int r)
{
if(l == 0) return prehsh[r];
int tmp = 1LL * prehsh[l - 1] * pw[r - l + 1] % mod;
int res = modit(prehsh[r] + mod - tmp);
return res;
}
void Build(int ty , int node = 1 , int nl = 0 , int nr = maxn)
{
tree[ty][node] = -1;
if(nl + 1 == nr) return;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Build(ty , lc , nl , mid); Build(ty , rc , mid , nr);
}
void Add(int ty , int l , int r , int val , int node = 1 , int nl = 0 , int nr = maxn)
{
if(r <= nl || nr <= l) return;
if(l <= nl && nr <= r)
{
tree[ty][node] = val;
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(tree[ty][node] != -1)
{
tree[ty][lc] = tree[ty][node];
tree[ty][rc] = tree[ty][node];
tree[ty][node] = -1;
}
Add(ty , l , r , val , lc , nl , mid); Add(ty , l , r ,val , rc , mid , nr);
}
int Get(int ty , int ind , int node = 1 , int nl = 0 , int nr = maxn)
{
if(tree[ty][node] != -1) return tree[ty][node];
assert(nl + 1 != nr);
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(ind < mid) return Get(ty , ind , lc , nl , mid);
else return Get(ty , ind , rc , mid , nr);
}
int solve(int l , int r)
{
if(Get(maxl - 1 , l) < r) return -1;
int low = 0 , high = (1 << (maxl - 1));
while(high - low > 1)
{
int mid = (high + low) >> 1;
int tmp = l;
for(int i = 0 ; i < maxl ; i++) if((mid >> i) & 1) tmp = Get(i , tmp);
if(tmp < r) low = mid;
else high = mid;
}
return high;
}
int32_t main()
{
fast;
for(int i = 0 ; i < maxl ; i++) Build(i);
pw[0] = 1;
for(int i = 1 ; i < maxn ; i++) pw[i] = 1LL * pw[i - 1] * Base % mod;
cin >> n >> m;
for(int i = 0 ; i < n ; i++)
{
string t; cin >> t;
int hsh = 0;
int tmp = t[0] - 'a' + 1;
tof[tmp] = 1;
for(int j = 0 ; j < SZ(t) ; j++)
{
hsh = 1LL * hsh * Base % mod;
hsh = modit(hsh + (t[j] - 'a' + 1));
marked[hsh] = true;
}
}
marked[0] = true;
cin >> s;
L = SZ(s);
for(int i = 0 ; i < m ; i++) cin >> ar[i].F >> ar[i].S;
prehsh[0] = s[0] - 'a' + 1;
for(int i = 1 ; i < L ; i++)
{
int now = s[i] - 'a' + 1;
prehsh[i] = 1LL * prehsh[i - 1] * Base % mod;
prehsh[i] = modit(prehsh[i] + now);
}
for(int i = 0 ; i < L ; i++)
{
int salam = s[i] - 'a' + 1;
if(tof[salam] != 1)
{
rr[i] = i;
continue;
}
int low = i , high = L;
while(high - low > 1)
{
int mid = (high + low) >> 1;
if(marked[get(i , mid)] && marked[get(i , mid - 1)]) low = mid;
else high = mid;
}
rr[i] = high;
}
for(int i = 0 ; i < maxl ; i++) Add(i , L , L + 1 , L);
for(int i = 0 ; i < m ; i++) vec[ar[i].F].pb({i , ar[i].S});
for(int i = L - 1 ; i > -1 ; i--)
{
int low = i , high = L;
while(high - low > 1)
{
int mid = (high + low) >> 1;
if(Get(0 , mid) < rr[i])
low = mid;
else
high = mid;
}
Add(0 , i , high , rr[i]);
for(int j = 1 ; j < maxl ; j++)
{
int tmp = Get(j - 1 , i);
tmp = Get(j - 1 , tmp);
Add(j , i , high , tmp);
}
for(auto u : vec[i])
ans[u.F] = solve(i , u.S);
}
for(int i = 0 ; i < m ; i++) cout << ans[i] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
90700 KB |
Output is correct |
| 2 |
Correct |
462 ms |
116032 KB |
Output is correct |
| 3 |
Incorrect |
460 ms |
111196 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2077 ms |
197096 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
90700 KB |
Output is correct |
| 2 |
Correct |
462 ms |
116032 KB |
Output is correct |
| 3 |
Incorrect |
460 ms |
111196 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
