oj.uz

Submission #1002692

# Submission time Handle Problem Language Result Execution time Memory
1002692 2024-06-19T18:14:31 Z aykhn Dabbeh (INOI20_dabbeh) C++17
25 / 100
 624 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 + 7;
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 137 ms 94432 KB Output is correct
2 Correct 291 ms 115536 KB Output is correct
3 Correct 273 ms 110740 KB Output is correct
4 Correct 317 ms 115540 KB Output is correct
5 Correct 296 ms 114048 KB Output is correct
6 Correct 337 ms 118608 KB Output is correct
7 Correct 271 ms 121160 KB Output is correct
8 Correct 335 ms 119888 KB Output is correct
9 Correct 310 ms 117584 KB Output is correct
10 Correct 226 ms 102136 KB Output is correct
11 Correct 239 ms 121876 KB Output is correct
12 Correct 201 ms 108824 KB Output is correct
13 Correct 194 ms 116128 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 624 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 137 ms 94432 KB Output is correct
2 Correct 291 ms 115536 KB Output is correct
3 Correct 273 ms 110740 KB Output is correct
4 Correct 317 ms 115540 KB Output is correct
5 Correct 296 ms 114048 KB Output is correct
6 Correct 337 ms 118608 KB Output is correct
7 Correct 271 ms 121160 KB Output is correct
8 Correct 335 ms 119888 KB Output is correct
9 Correct 310 ms 117584 KB Output is correct
10 Correct 226 ms 102136 KB Output is correct
11 Correct 239 ms 121876 KB Output is correct
12 Correct 201 ms 108824 KB Output is correct
13 Correct 194 ms 116128 KB Output is correct
14 Incorrect 624 ms 171144 KB Output isn't correct
15 Halted 0 ms 0 KB -