| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 771037 |
2023-07-02T11:28:19 Z |
parsadox2 |
Dabbeh (INOI20_dabbeh) |
C++14 |
|
2000 ms |
101388 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 = 1e9 + 7 , Base = 131 , maxl = 20 , mod2 = 2000000357;
int n , m , L , pw[maxn] , prehsh[2][maxn] , tree[maxl][maxn << 2] , rr[maxn] , ans[maxn];
pair<int , int> ar[maxn];
string s;
vector <pair<int , int>> vec[maxn] , allh;
inline int modit(int a , int mm)
{
if(a >= mm) a -= mm;
return a;
}
inline pair<int , int> get(int l , int r)
{
if(l == 0) return make_pair(prehsh[0][r] , prehsh[1][r]);
int tmp = 1LL * prehsh[0][l - 1] * pw[r - l + 1] % mod;
int res = modit(prehsh[0][r] + mod - tmp , mod);
int tmp2 = 1LL * prehsh[1][l - 1] * pw[r - l + 1] % mod2;
int res2 = modit(prehsh[1][r] + mod2 - tmp2 , mod2);
return make_pair(res , res2);
}
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);
}
inline 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 hsh0 = 0 , hsh1 = 0;
for(int j = 0 ; j < SZ(t) ; j++)
{
hsh0 = 1LL * hsh0 * Base % mod;
hsh0 = modit(hsh0 + (t[j] - 'a' + 1) , mod);
hsh1 = 1LL * hsh1 * Base % mod2;
hsh1 = modit(hsh1 + (t[j] - 'a' + 1) , mod2);
allh.pb({hsh0 , hsh1});
}
}
allh.pb({0 , 0});
sort(allh.begin() , allh.end());
cin >> s;
L = SZ(s);
for(int i = 0 ; i < m ; i++) cin >> ar[i].F >> ar[i].S;
prehsh[0][0] = prehsh[1][0] = s[0] - 'a' + 1;
for(int i = 1 ; i < L ; i++)
{
int now = s[i] - 'a' + 1;
prehsh[0][i] = 1LL * prehsh[0][i - 1] * Base % mod;
prehsh[0][i] = modit(prehsh[0][i] + now , mod);
prehsh[1][i] = 1LL * prehsh[1][i - 1] * Base % mod2;
prehsh[1][i] = modit(prehsh[1][i] + now , mod2);
}
for(int i = 0 ; i < L ; i++)
{
int low = i - 1 , high = L;
while(high - low > 1)
{
int mid = (high + low) >> 1;
auto now = get(i , mid);
int pos1 = lower_bound(allh.begin() , allh.end() , now) - allh.begin();
int pos2 = upper_bound(allh.begin() , allh.end() , now) - allh.begin();
if(pos1 != pos2) 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 |
43 ms |
90700 KB |
Output is correct |
| 2 |
Correct |
359 ms |
101388 KB |
Output is correct |
| 3 |
Incorrect |
388 ms |
100576 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
96152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
90700 KB |
Output is correct |
| 2 |
Correct |
359 ms |
101388 KB |
Output is correct |
| 3 |
Incorrect |
388 ms |
100576 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
