oj.uz

Submission #1002003

# Submission time Handle Problem Language Result Execution time Memory
1002003 2024-06-19T09:06:33 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
0 / 100
 1342 ms 208096 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 < 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++;
    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 (nxt[l] > r) cout << res + 1 << '\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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 110176 KB Output is correct
2 Correct 726 ms 137056 KB Output is correct
3 Incorrect 667 ms 130644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1049 ms 191876 KB Output is correct
2 Correct 1181 ms 199372 KB Output is correct
3 Correct 1037 ms 192996 KB Output is correct
4 Correct 1029 ms 186188 KB Output is correct
5 Correct 1006 ms 185932 KB Output is correct
6 Correct 1342 ms 199816 KB Output is correct
7 Correct 1251 ms 203136 KB Output is correct
8 Correct 1251 ms 196264 KB Output is correct
9 Correct 1262 ms 200560 KB Output is correct
10 Correct 1255 ms 205336 KB Output is correct
11 Correct 1136 ms 193368 KB Output is correct
12 Correct 1068 ms 191204 KB Output is correct
13 Incorrect 1249 ms 208096 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 110176 KB Output is correct
2 Correct 726 ms 137056 KB Output is correct
3 Incorrect 667 ms 130644 KB Output isn't correct
4 Halted 0 ms 0 KB -