oj.uz

Submission #1002029

# Submission time Handle Problem Language Result Execution time Memory
1002029 2024-06-19T09:24:16 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
100 / 100
 1914 ms 216956 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 1e6 + 5;
const int LOG = 20;
const __int128 mod = 1000000000000000009;
const __int128 base = 9128398;
 
__int128 read() {
  __int128 x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
void print(__int128 x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
bool cmp(__int128 x, __int128 y) { return x > y; }
 
__int128 ph[2][MXN], p[MXN], invp[MXN];
 
__int128 mult(__int128 a, __int128 b)
{
  return (a * b) % mod;
}
 
__int128 add(__int128 a, __int128 b)
{
  return (a + b) % mod;
}
 
__int128 pw(__int128 a, __int128 b, __int128 c)
{
  a %= c;
  __int128 res = 1;
  while (b)
  {
    if (b & 1) res = mult(res, a);
    a = mult(a, a);
    b >>= 1;
  }
  return res;
}
 
__int128 get_hash(int l, int r, int id)
{
  return mult(add(ph[id][r], mod - ph[id][l - 1]), invp[l]);
}
 
void _HASH(string &s, int id)
{
  int n = (int)s.length() - 1;
  ph[id][0] = 0;
  for (int i = 1; i <= n; i++) ph[id][i] = add(ph[id][i - 1], mult(p[i], s[i] - 'a' + 1));
}

array<int, 2> st[MXN << 2];
int par[LOG][MXN];
void make(int l, int r, int x, int ind, int val)
{
  if (l == r)
  {
    st[x] = {val, ind};
    return;
  }
  int mid = (l + r) >> 1;
  if (ind <= mid)  make(l, mid, 2*x, ind, val);
  else make(mid + 1, r, 2*x + 1, ind, val);
  st[x] = max(st[2*x], st[2*x + 1]);
}
array<int, 2> get(int l, int r, int x, int lx, int rx)
{
  if (l > rx || r < lx) return {0, 0};
  if (l >= lx && r <= rx) return st[x];
  int mid = (l + r) >> 1;
  return max(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx));
}

int L, n, k;
string t[MXN], s;
set<__int128> mp[MXN];
int nxt[MXN];

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  p[0] = 1;
  for (int i = 1; i < MXN; i++) p[i] = mult(p[i - 1], base);
  for (int i = 0; i < MXN; i++) invp[i] = pw(p[i], mod - 2, mod);
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> t[i];
  cin >> s;
  L = s.length();
  s = "#" + s;
  _HASH(s, 0);
  for (int i = 0; i < n; i++)
  {
    t[i] = "#" + t[i];
    _HASH(t[i], 1);
    for (int j = 1; j < t[i].length(); j++) mp[j].insert(get_hash(1, j, 1));
  }
  for (int i = 1; i <= L; i++)
  {
    if (mp[1].find(get_hash(i, i, 0)) == mp[1].end()) nxt[i] = 0;
    else
    {
      int l = i, r = L;
      while (l < r)
      {
        int mid = (l + r + 1) >> 1;
        if (mp[mid - i + 1].find(get_hash(i, mid, 0)) != mp[mid - i + 1].end()) l = mid;
        else r = mid - 1;
      }
      nxt[i] = l + 1;
    }
  }
  for (int i = 1; i <= L; i++) if (nxt[i]) make(1, L, 1, i, nxt[i]);
  for (int i = 1; i <= L; i++)
  {
    array<int, 2> j = get(1, L, 1, i, nxt[i]);
    if (j[0] > nxt[i]) 
    {
      par[0][i] = j[1];
    }
  }
  // for (int i = 1; i <= L; i++) cout << nxt[i] << ' ';
  // cout << '\n';
  // for (int i = 1; i <= L; i++) cout << par[0][i] << ' '; 
  // cout << '\n';
  // for (int i = 1; i <= L; i++) if (nxt[i] && !par[0][i]) par[0][i] = nxt[i];
  for (int i = 1; i < LOG; i++) for (int j = 1; j <= L; j++) par[i][j] = par[i - 1][par[i - 1][j]];
  while (k--)
  {
    int l, r, res = 0;
    cin >> l >> r;
    l++;
    if (nxt[l] > r) 
    {
      cout << 1 << '\n';
      continue;
    }
    for (int i = LOG - 1; i >= 0; i--)
    {
      if (!par[i][l] || nxt[par[i][l]] > r) continue;
      l = par[i][l];
      res |= (1LL << i);
    }
    if (nxt[par[0][l]] > r) cout << res + 2 << '\n';
    else cout << -1 << '\n';
  }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:117: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]
  117 |     for (int j = 1; j < t[i].length(); j++) mp[j].insert(get_hash(1, j, 1));
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 110164 KB Output is correct
2 Correct 741 ms 136940 KB Output is correct
3 Correct 716 ms 130752 KB Output is correct
4 Correct 754 ms 136788 KB Output is correct
5 Correct 733 ms 134772 KB Output is correct
6 Correct 822 ms 140884 KB Output is correct
7 Correct 740 ms 144468 KB Output is correct
8 Correct 808 ms 142528 KB Output is correct
9 Correct 766 ms 139604 KB Output is correct
10 Correct 653 ms 119380 KB Output is correct
11 Correct 678 ms 147776 KB Output is correct
12 Correct 648 ms 129296 KB Output is correct
13 Correct 677 ms 139684 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1149 ms 191880 KB Output is correct
2 Correct 1231 ms 199588 KB Output is correct
3 Correct 1065 ms 193172 KB Output is correct
4 Correct 1073 ms 186420 KB Output is correct
5 Correct 1043 ms 185928 KB Output is correct
6 Correct 1383 ms 199648 KB Output is correct
7 Correct 1357 ms 202892 KB Output is correct
8 Correct 1272 ms 196436 KB Output is correct
9 Correct 1382 ms 200560 KB Output is correct
10 Correct 1319 ms 205332 KB Output is correct
11 Correct 1254 ms 193364 KB Output is correct
12 Correct 1090 ms 191572 KB Output is correct
13 Correct 1361 ms 207928 KB Output is correct
14 Correct 1231 ms 204856 KB Output is correct
15 Correct 953 ms 183244 KB Output is correct
16 Correct 761 ms 212008 KB Output is correct
17 Correct 790 ms 190308 KB Output is correct
18 Correct 770 ms 190064 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 110164 KB Output is correct
2 Correct 741 ms 136940 KB Output is correct
3 Correct 716 ms 130752 KB Output is correct
4 Correct 754 ms 136788 KB Output is correct
5 Correct 733 ms 134772 KB Output is correct
6 Correct 822 ms 140884 KB Output is correct
7 Correct 740 ms 144468 KB Output is correct
8 Correct 808 ms 142528 KB Output is correct
9 Correct 766 ms 139604 KB Output is correct
10 Correct 653 ms 119380 KB Output is correct
11 Correct 678 ms 147776 KB Output is correct
12 Correct 648 ms 129296 KB Output is correct
13 Correct 677 ms 139684 KB Output is correct
14 Correct 1149 ms 191880 KB Output is correct
15 Correct 1231 ms 199588 KB Output is correct
16 Correct 1065 ms 193172 KB Output is correct
17 Correct 1073 ms 186420 KB Output is correct
18 Correct 1043 ms 185928 KB Output is correct
19 Correct 1383 ms 199648 KB Output is correct
20 Correct 1357 ms 202892 KB Output is correct
21 Correct 1272 ms 196436 KB Output is correct
22 Correct 1382 ms 200560 KB Output is correct
23 Correct 1319 ms 205332 KB Output is correct
24 Correct 1254 ms 193364 KB Output is correct
25 Correct 1090 ms 191572 KB Output is correct
26 Correct 1361 ms 207928 KB Output is correct
27 Correct 1231 ms 204856 KB Output is correct
28 Correct 953 ms 183244 KB Output is correct
29 Correct 761 ms 212008 KB Output is correct
30 Correct 790 ms 190308 KB Output is correct
31 Correct 770 ms 190064 KB Output is correct
32 Correct 1045 ms 162056 KB Output is correct
33 Correct 1254 ms 175232 KB Output is correct
34 Correct 1253 ms 182464 KB Output is correct
35 Correct 1168 ms 179256 KB Output is correct
36 Correct 1168 ms 186620 KB Output is correct
37 Correct 1010 ms 161612 KB Output is correct
38 Correct 1898 ms 211832 KB Output is correct
39 Correct 1522 ms 197792 KB Output is correct
40 Correct 1914 ms 216120 KB Output is correct
41 Correct 1743 ms 216956 KB Output is correct
42 Correct 1509 ms 204576 KB Output is correct
43 Correct 1031 ms 154504 KB Output is correct
44 Correct 950 ms 152996 KB Output is correct
45 Correct 904 ms 152388 KB Output is correct
46 Correct 1083 ms 163256 KB Output is correct
47 Correct 1257 ms 190816 KB Output is correct
48 Correct 1419 ms 199948 KB Output is correct
49 Correct 1327 ms 191856 KB Output is correct
50 Correct 1630 ms 213824 KB Output is correct
51 Correct 857 ms 188812 KB Output is correct
52 Correct 739 ms 196260 KB Output is correct
53 Correct 812 ms 189468 KB Output is correct