oj.uz

Submission #1002001

# Submission time Handle Problem Language Result Execution time Memory
1002001 2024-06-19T09:05:30 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
0 / 100
 1513 ms 208268 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 = 1031;
 
__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 646 ms 110164 KB Output is correct
2 Correct 877 ms 137044 KB Output is correct
3 Incorrect 802 ms 130744 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1253 ms 191716 KB Output is correct
2 Correct 1513 ms 199408 KB Output is correct
3 Correct 1176 ms 193224 KB Output is correct
4 Correct 1086 ms 186164 KB Output is correct
5 Correct 1036 ms 185924 KB Output is correct
6 Correct 1306 ms 199588 KB Output is correct
7 Correct 1320 ms 202880 KB Output is correct
8 Correct 1239 ms 196440 KB Output is correct
9 Correct 1289 ms 200808 KB Output is correct
10 Correct 1307 ms 205432 KB Output is correct
11 Correct 1106 ms 193484 KB Output is correct
12 Correct 1128 ms 191216 KB Output is correct
13 Incorrect 1384 ms 208268 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 110164 KB Output is correct
2 Correct 877 ms 137044 KB Output is correct
3 Incorrect 802 ms 130744 KB Output isn't correct
4 Halted 0 ms 0 KB -