oj.uz

Submission #1002694

# Submission time Handle Problem Language Result Execution time Memory
1002694 2024-06-19T18:16:09 Z aykhn Dabbeh (INOI20_dabbeh) C++17
25 / 100
 663 ms 171144 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 = 1e9 + 861;
const int base = 9128398;
 
int ph[2][MXN], p[MXN], invp[MXN];
 
int mult(int a, int b)
{
  return (a * b) % mod;
}
 
int add(int a, int b)
{
  return (a + b) % 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 157 ms 94548 KB Output is correct
2 Correct 315 ms 113472 KB Output is correct
3 Correct 276 ms 108368 KB Output is correct
4 Correct 344 ms 112976 KB Output is correct
5 Correct 306 ms 111320 KB Output is correct
6 Correct 384 ms 116020 KB Output is correct
7 Correct 287 ms 118352 KB Output is correct
8 Correct 376 ms 118900 KB Output is correct
9 Correct 303 ms 116572 KB Output is correct
10 Correct 230 ms 101204 KB Output is correct
11 Correct 232 ms 121020 KB Output is correct
12 Correct 204 ms 107832 KB Output is correct
13 Correct 208 ms 115104 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 663 ms 171144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 94548 KB Output is correct
2 Correct 315 ms 113472 KB Output is correct
3 Correct 276 ms 108368 KB Output is correct
4 Correct 344 ms 112976 KB Output is correct
5 Correct 306 ms 111320 KB Output is correct
6 Correct 384 ms 116020 KB Output is correct
7 Correct 287 ms 118352 KB Output is correct
8 Correct 376 ms 118900 KB Output is correct
9 Correct 303 ms 116572 KB Output is correct
10 Correct 230 ms 101204 KB Output is correct
11 Correct 232 ms 121020 KB Output is correct
12 Correct 204 ms 107832 KB Output is correct
13 Correct 208 ms 115104 KB Output is correct
14 Incorrect 663 ms 171144 KB Output isn't correct
15 Halted 0 ms 0 KB -