Submission #1001785

#TimeUsernameProblemLanguageResultExecution timeMemory
1001785vjudge1Dabbeh (INOI20_dabbeh)C++17
0 / 100
412 ms91428 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define inf 0x3F3F3F3F3F3F3F3F const int MXN = 3e5 + 5; const int LOG = 20; 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 n, k, m; string s, t[MXN]; int par[LOG][MXN]; int inter(array<int, 2> x, array<int, 2> y) { return max(x[0], y[0]) <= min(x[1], y[1]); } 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); } cin >> k >> m; for (int i = 0; i < k; i++) cin >> t[i]; cin >> s; 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.find({get_hash(i, i, 0), get_hash(i, i, 1)}) == mp.end()) { continue; } while (l < r) { int mid = (l + r + 1) >> 1; if (mp.find({get_hash(i, i, 0), get_hash(i, i, 1)}) != mp.end()) l = mid; else r = mid - 1; } R[i] = l + 1; } vector<array<int, 2>> v; for (int i = n; i >= 1; i--) { if (v.empty() || !R[i]) { par[0][i] = 0; } else { int l = 0, r = (int)v.size() - 1; while (l < r) { int mid = (l + r) >> 1; if (v[mid][1] > R[i]) l = mid + 1; else r = mid; } if (v[r][1] <= R[i]) par[0][i] = v[r][1]; } if (R[i]) { while (!v.empty() && v.back()[0] <= R[i]) v.pop_back(); v.push_back({R[i], i}); } } for (int i = 1; i < LOG; i++) for (int j = 1; j <= n; j++) par[i][j] = par[i - 1][par[i - 1][j]]; for (int i = 0; i < m; i++) { int l, r, res = 0; cin >> l >> r; l++; for (int i = LOG - 1; i >= 0; i--) { if (!par[i][l] || par[i][l] > r) continue; l = par[i][l]; res |= (1LL << i); } if (!par[0][l] || R[l] <= r) cout << -1 << '\n'; else cout << res + 1 << '\n'; } }

Compilation message (stderr)

Main.cpp: In function 'void _HASH(std::string&, long long int)':
Main.cpp:80: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]
   80 |   for (int i = 1; i < s.length(); i++)
      |                   ~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:121: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]
  121 |     for (int j = 0; j < t[i].length(); j++)
      |                     ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...