| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1001653 |
2024-06-19T06:44:08 Z |
vjudge1 |
Dabbeh (INOI20_dabbeh) |
C++17 |
|
2000 ms |
178896 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3F3F3F3F
const int MXN = 3e5 + 5;
const int mod = 1e9 + 7;
int b1, b2;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int st[MXN << 2];
int lz[MXN << 2];
void relax(int l, int r, int x)
{
if (!lz[x]) return;
st[x] = (r - l + 1);
lz[x] = 0;
if (l == r) return;
lz[2*x] = lz[2*x + 1] = 1;
}
void make(int l, int r, int x, int lx, int rx)
{
relax(l, r, x);
if (l > rx || r < lx) return;
if (l >= lx && r <= rx)
{
lz[x] = 1;
relax(l, r, x);
return;
}
int mid = (l + r) >> 1;
make(l, mid, 2*x, lx, rx);
make(mid + 1, r, 2*x + 1, lx, rx);
st[x] = st[2*x] + st[2*x + 1];
}
int get(int l, int r, int x, int lx, int rx)
{
if (l > rx || r < lx) return 0;
relax(l, r, x);
if (l >= lx && r <= rx) return st[x];
int mid = (l + r) >> 1;
return get(l, mid, 2*x, lx, rx) + get(mid + 1, r, 2*x + 1, lx, rx);
}
int add(int a, int b)
{
return (a + b + mod) % mod;
}
int mult(int a, int b)
{
return (a * b) % mod;
}
int pw(int a, int b, int c)
{
a %= c;
int res = 1;
while (b)
{
if (b & 1) res = mult(res, a);
a = mult(a, a);
b >>= 1;
}
return res;
}
int ph[2][MXN], p[2][MXN], invp[2][MXN];
int get_hash(int l, int r, int id)
{
return mult(add(ph[id][r], -ph[id][l - 1]), invp[id][l]);
}
void _HASH(string &s, int id)
{
for (int i = 1; i < s.length(); i++)
{
ph[id][i] = add(ph[id][i - 1], mult(p[id][i], s[i] - 'a' + 1));
}
}
map<array<int, 2>, int> mp;
int R[MXN];
int ans[MXN];
vector<array<int, 2>> q[MXN];
int inter(array<int, 2> x, array<int, 2> y)
{
return max(x[0], y[0]) <= min(x[1], y[1]);
}
// int dp[505][505];
// int f(int l, int r)
// {
// // cout << l << ' ' << r << ' ' << get_hash(l, r, 0) << ' ' << get_hash(l, r, 1) << '\n';
// if (mp[{get_hash(l, r, 0), get_hash(l, r, 1)}]) return 1;
// if (dp[l][r] != -1) return dp[l][r];
// dp[l][r] = inf;
// for (int i = l; i <= r; i++)
// {
// if (mp[{get_hash(l, i, 0), get_hash(l, i, 1)}]) dp[l][r] = min(dp[l][r], f(i + 1, r) + 1);
// }
// // cout << "ANS: " << l << ' ' << r << ' ' << dp[l][r] << '\n';
// return dp[l][r];
// }
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
b1 = rng() % (mod - 1) + 1, b2 = rng() % (mod - 1) + 1;
p[0][0] = p[1][0] = 1, invp[0][0] = invp[1][0] = 1;
for (int i = 1; i < MXN; i++)
{
p[0][i] = mult(p[0][i - 1], b1);
p[1][i] = mult(p[1][i - 1], b2);
invp[0][i] = pw(p[0][i], mod - 2, mod);
invp[1][i] = pw(p[1][i], mod - 2, mod);
}
int k, m;
cin >> k >> m;
string t[k];
for (int i = 0; i < k; i++) cin >> t[i];
string s;
cin >> s;
int n = s.length();
s = "#" + s;
_HASH(s, 0);
_HASH(s, 1);
for (int i = 0; i < k; i++)
{
int h1 = 0, h2 = 0;
for (int j = 0; j < t[i].length(); j++)
{
h1 = add(h1, mult(t[i][j] - 'a' + 1, p[0][j]));
h2 = add(h2, mult(t[i][j] - 'a' + 1, p[1][j]));
mp[{h1, h2}] = 1;
}
}
for (int i = 1; i <= n; i++)
{
int l = i, r = n;
if (!mp[{get_hash(i, i, 0), get_hash(i, i, 1)}])
{
continue;
}
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (mp[{get_hash(i, mid, 0), get_hash(i, mid, 1)}]) l = mid;
else r = mid - 1;
}
R[i] = l;
}
for (int i = 0; i < m; i++)
{
int l, r;
cin >> l >> r;
l++;
q[l].push_back({r, i});
}
vector<array<int, 2>> v;
for (int i = n; i >= 1; i--)
{
if (R[i])
{
make(1, n, 1, i, R[i]);
while (!v.empty())
{
if (v.back()[1] <= R[i]) v.pop_back();
else if (v.size() > 1 && inter(*prev(prev(v.end())), {i, R[i]})) v.pop_back();
else break;
}
v.push_back({i, R[i]});
}
for (array<int, 2> &j : q[i])
{
if (get(1, n, 1, i, j[0]) != j[0] - i + 1)
{
ans[j[1]] = -1;
continue;
}
int l = 0, r = (int)v.size() - 1;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (v[mid][1] >= j[0]) l = mid;
else r = mid - 1;
}
ans[j[1]] = (int)v.size() - l;
}
}
for (int i = 0; i < m; i++) cout << ans[i] << '\n';
}
Compilation message
Main.cpp: In function 'void _HASH(std::string&, long long int)':
Main.cpp:79:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = 1; i < s.length(); i++)
| ~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:135:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for (int j = 0; j < t[i].length(); j++)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
16720 KB |
Output is correct |
| 2 |
Incorrect |
351 ms |
50512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2009 ms |
178896 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
16720 KB |
Output is correct |
| 2 |
Incorrect |
351 ms |
50512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
