oj.uz

Submission #1002687

# Submission time Handle Problem Language Result Execution time Memory
1002687 2024-06-19T18:12:19 Z aykhn Dabbeh (INOI20_dabbeh) C++17
100 / 100
 1934 ms 217072 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 583 ms 110160 KB Output is correct
2 Correct 764 ms 137044 KB Output is correct
3 Correct 715 ms 130644 KB Output is correct
4 Correct 845 ms 136860 KB Output is correct
5 Correct 773 ms 134844 KB Output is correct
6 Correct 856 ms 140796 KB Output is correct
7 Correct 744 ms 144472 KB Output is correct
8 Correct 820 ms 142672 KB Output is correct
9 Correct 759 ms 139556 KB Output is correct
10 Correct 643 ms 119380 KB Output is correct
11 Correct 626 ms 147920 KB Output is correct
12 Correct 603 ms 129300 KB Output is correct
13 Correct 624 ms 139520 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1092 ms 191740 KB Output is correct
2 Correct 1131 ms 199584 KB Output is correct
3 Correct 1124 ms 193104 KB Output is correct
4 Correct 981 ms 186300 KB Output is correct
5 Correct 1109 ms 185832 KB Output is correct
6 Correct 1477 ms 199772 KB Output is correct
7 Correct 1464 ms 202984 KB Output is correct
8 Correct 1369 ms 196392 KB Output is correct
9 Correct 1458 ms 200560 KB Output is correct
10 Correct 1505 ms 205348 KB Output is correct
11 Correct 1197 ms 193376 KB Output is correct
12 Correct 1174 ms 191256 KB Output is correct
13 Correct 1444 ms 208128 KB Output is correct
14 Correct 1331 ms 204848 KB Output is correct
15 Correct 927 ms 183272 KB Output is correct
16 Correct 730 ms 212004 KB Output is correct
17 Correct 706 ms 190536 KB Output is correct
18 Correct 718 ms 189956 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 110160 KB Output is correct
2 Correct 764 ms 137044 KB Output is correct
3 Correct 715 ms 130644 KB Output is correct
4 Correct 845 ms 136860 KB Output is correct
5 Correct 773 ms 134844 KB Output is correct
6 Correct 856 ms 140796 KB Output is correct
7 Correct 744 ms 144472 KB Output is correct
8 Correct 820 ms 142672 KB Output is correct
9 Correct 759 ms 139556 KB Output is correct
10 Correct 643 ms 119380 KB Output is correct
11 Correct 626 ms 147920 KB Output is correct
12 Correct 603 ms 129300 KB Output is correct
13 Correct 624 ms 139520 KB Output is correct
14 Correct 1092 ms 191740 KB Output is correct
15 Correct 1131 ms 199584 KB Output is correct
16 Correct 1124 ms 193104 KB Output is correct
17 Correct 981 ms 186300 KB Output is correct
18 Correct 1109 ms 185832 KB Output is correct
19 Correct 1477 ms 199772 KB Output is correct
20 Correct 1464 ms 202984 KB Output is correct
21 Correct 1369 ms 196392 KB Output is correct
22 Correct 1458 ms 200560 KB Output is correct
23 Correct 1505 ms 205348 KB Output is correct
24 Correct 1197 ms 193376 KB Output is correct
25 Correct 1174 ms 191256 KB Output is correct
26 Correct 1444 ms 208128 KB Output is correct
27 Correct 1331 ms 204848 KB Output is correct
28 Correct 927 ms 183272 KB Output is correct
29 Correct 730 ms 212004 KB Output is correct
30 Correct 706 ms 190536 KB Output is correct
31 Correct 718 ms 189956 KB Output is correct
32 Correct 945 ms 162180 KB Output is correct
33 Correct 1174 ms 175428 KB Output is correct
34 Correct 1190 ms 182580 KB Output is correct
35 Correct 1182 ms 179080 KB Output is correct
36 Correct 1284 ms 186624 KB Output is correct
37 Correct 1034 ms 161520 KB Output is correct
38 Correct 1934 ms 212024 KB Output is correct
39 Correct 1668 ms 197928 KB Output is correct
40 Correct 1879 ms 216012 KB Output is correct
41 Correct 1548 ms 217072 KB Output is correct
42 Correct 1447 ms 204728 KB Output is correct
43 Correct 978 ms 154544 KB Output is correct
44 Correct 995 ms 153196 KB Output is correct
45 Correct 951 ms 152236 KB Output is correct
46 Correct 1094 ms 163256 KB Output is correct
47 Correct 1258 ms 190952 KB Output is correct
48 Correct 1437 ms 199908 KB Output is correct
49 Correct 1355 ms 191880 KB Output is correct
50 Correct 1618 ms 214012 KB Output is correct
51 Correct 852 ms 188800 KB Output is correct
52 Correct 773 ms 196196 KB Output is correct
53 Correct 875 ms 189496 KB Output is correct