oj.uz

Submission #1002695

# Submission time Handle Problem Language Result Execution time Memory
1002695 2024-06-19T18:18:03 Z aykhn Dabbeh (INOI20_dabbeh) C++17
100 / 100
 1669 ms 191736 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 int mod = 1000000000000000009;
const int base = 9128398;
 
int ph[2][MXN], p[MXN], invp[MXN];
 
int mult(int a, int b)
{
  return ((__int128)a * (__int128)b) % mod;
}
 
int add(int a, int b)
{
  return ((__int128)a + (__int128)b + (__int128)mod) % 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 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<int> 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 < 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:94: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]
   94 |     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 593 ms 94544 KB Output is correct
2 Correct 761 ms 115540 KB Output is correct
3 Correct 678 ms 110672 KB Output is correct
4 Correct 788 ms 115580 KB Output is correct
5 Correct 720 ms 114000 KB Output is correct
6 Correct 741 ms 118608 KB Output is correct
7 Correct 678 ms 121192 KB Output is correct
8 Correct 716 ms 119888 KB Output is correct
9 Correct 712 ms 117588 KB Output is correct
10 Correct 657 ms 102096 KB Output is correct
11 Correct 622 ms 121876 KB Output is correct
12 Correct 616 ms 109048 KB Output is correct
13 Correct 622 ms 116132 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1089 ms 171144 KB Output is correct
2 Correct 1224 ms 176920 KB Output is correct
3 Correct 999 ms 172456 KB Output is correct
4 Correct 942 ms 166916 KB Output is correct
5 Correct 940 ms 166852 KB Output is correct
6 Correct 1145 ms 177204 KB Output is correct
7 Correct 1201 ms 179744 KB Output is correct
8 Correct 1139 ms 174628 KB Output is correct
9 Correct 1187 ms 177872 KB Output is correct
10 Correct 1177 ms 181628 KB Output is correct
11 Correct 1035 ms 172416 KB Output is correct
12 Correct 982 ms 170852 KB Output is correct
13 Correct 1221 ms 183384 KB Output is correct
14 Correct 1169 ms 181240 KB Output is correct
15 Correct 887 ms 164740 KB Output is correct
16 Correct 728 ms 184268 KB Output is correct
17 Correct 709 ms 169144 KB Output is correct
18 Correct 746 ms 169112 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 94544 KB Output is correct
2 Correct 761 ms 115540 KB Output is correct
3 Correct 678 ms 110672 KB Output is correct
4 Correct 788 ms 115580 KB Output is correct
5 Correct 720 ms 114000 KB Output is correct
6 Correct 741 ms 118608 KB Output is correct
7 Correct 678 ms 121192 KB Output is correct
8 Correct 716 ms 119888 KB Output is correct
9 Correct 712 ms 117588 KB Output is correct
10 Correct 657 ms 102096 KB Output is correct
11 Correct 622 ms 121876 KB Output is correct
12 Correct 616 ms 109048 KB Output is correct
13 Correct 622 ms 116132 KB Output is correct
14 Correct 1089 ms 171144 KB Output is correct
15 Correct 1224 ms 176920 KB Output is correct
16 Correct 999 ms 172456 KB Output is correct
17 Correct 942 ms 166916 KB Output is correct
18 Correct 940 ms 166852 KB Output is correct
19 Correct 1145 ms 177204 KB Output is correct
20 Correct 1201 ms 179744 KB Output is correct
21 Correct 1139 ms 174628 KB Output is correct
22 Correct 1187 ms 177872 KB Output is correct
23 Correct 1177 ms 181628 KB Output is correct
24 Correct 1035 ms 172416 KB Output is correct
25 Correct 982 ms 170852 KB Output is correct
26 Correct 1221 ms 183384 KB Output is correct
27 Correct 1169 ms 181240 KB Output is correct
28 Correct 887 ms 164740 KB Output is correct
29 Correct 728 ms 184268 KB Output is correct
30 Correct 709 ms 169144 KB Output is correct
31 Correct 746 ms 169112 KB Output is correct
32 Correct 976 ms 143880 KB Output is correct
33 Correct 1173 ms 154052 KB Output is correct
34 Correct 1251 ms 159536 KB Output is correct
35 Correct 1203 ms 156812 KB Output is correct
36 Correct 1112 ms 162508 KB Output is correct
37 Correct 972 ms 143688 KB Output is correct
38 Correct 1585 ms 187840 KB Output is correct
39 Correct 1390 ms 177120 KB Output is correct
40 Correct 1669 ms 191140 KB Output is correct
41 Correct 1553 ms 191736 KB Output is correct
42 Correct 1492 ms 182204 KB Output is correct
43 Correct 956 ms 133988 KB Output is correct
44 Correct 913 ms 133032 KB Output is correct
45 Correct 934 ms 132272 KB Output is correct
46 Correct 1016 ms 140728 KB Output is correct
47 Correct 1167 ms 171932 KB Output is correct
48 Correct 1428 ms 178708 KB Output is correct
49 Correct 1184 ms 172784 KB Output is correct
50 Correct 1605 ms 189344 KB Output is correct
51 Correct 835 ms 169524 KB Output is correct
52 Correct 794 ms 174672 KB Output is correct
53 Correct 895 ms 170136 KB Output is correct