oj.uz

Submission #1001642

# Submission time Handle Problem Language Result Execution time Memory
1001642 2024-06-19T06:41:37 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
0 / 100
 328 ms 109032 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")

namespace hsg {
  mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
  const long long mod = (long long)1e18+9;
  long long R=rng()%(mod);
  struct PolyHash {
    vector<long long> pref,pw;
    int n;
    PolyHash(string s) {
      n = s.size();
      pref.resize(n+1);
      pw.resize(n+1);
      pw[0]=1;
      for(int i = 1;i<=n;i++) {
        pref[i] = ((__int128_t)pref[i-1]*R)%mod;
        pref[i]+=s[i-1];
        pref[i]%=mod;
        pw[i] = ((__int128_t)pw[i-1]*R)%mod;
      }
    }
    long long get(int l, int r) {
 
      long long hs=(pref[r]-((__int128_t)pref[l-1]*pw[r-l+1])%mod + mod)%mod;
      return hs;
    }
  };
};
const int LL = 3e5+10;
const int LG = 20;
int up[LL][LG];
int nxt[LL];
bool cmp(const string& A, const string &B)  {
  return A.size() < B.size();
};
int get(int l, int r) {
  int at = l;
  long long ans=1;
  if(nxt[at] >= r)return 1;
  for(int i = LG-1;i>=0;i--) {
    if(nxt[up[at][i]] < r) {
      at = up[at][i];
      ans+=(1<<i);
    }
  }
  if(nxt[up[at][0]] < r)return -1;
  return ans+1;
}
int get2(int l, int r) {
  int at = l;
  int ans=1;
  while(nxt[at] < r) {
    if(at == up[at][0]) {
      return -1;
    }
    at = up[at][0];
    ans++;
  }
  return ans;
}
int main () {
  cin.tie(0)->sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  string s[n];
  for(int i =0;i<n;i++) {
    cin >> s[i];
  }
  sort(s, s+n, cmp);
  string S;
  cin >> S;
  int L = S.size();
  vector<pair<int,int>> inv;
  memset(nxt, -1, sizeof nxt);
  hsg::PolyHash hs(S);
  vector<long long> mp[L+1];
  for(int i = 0;i<n;i++) {
    hsg::PolyHash hss(s[i]);
    for(int j = 0 ;j<min(L, (int)s[i].size());j++) {
      mp[j+1].push_back(hss.get(1, j+1));
    }
  }
  for(int i = 0;i<=L;i++)sort(mp[i].begin(), mp[i].end());
  for(int i = 0;i<L;i++)nxt[i]=i;
  for(int i = 0;i<L;i++) {
    nxt[i]=i;
    int lo = 1, hi = L-i;
    while(lo <= hi) {
      int mid = (lo+hi)/2;
      long long hsss = hs.get(i+1, i+mid);
      auto it = lower_bound(mp[mid].begin(), mp[mid].end(), hsss);
      if(it != mp[mid].end() and (*it) == hsss) {
        nxt[i] = i+mid;
        lo = mid+1;
      }
      else {
        hi=mid-1;
      }
    }
  }
  {
    vector<int> v[L+1];
    for(int i= 0;i<L;i++) {
      v[nxt[i]].push_back(i);
    }
    vector<int> stk;
    for(int i = 0;i<L;i++) {
      while(stk.size() and nxt[stk.back()] <= nxt[i]) {
        stk.pop_back();
      }
      stk.push_back(i);
      for(int j:v[i]){
        int idx = (*lower_bound(stk.begin(), stk.end(), j));
        up[j][0] = idx;
      }
    }
    for(int i = L-1;i>=0;i--) {
      for(int j = 1;j<LG;j++)up[i][j] = up[up[i][j-1]][j-1];
    }
  }
  while(m--) {
    int l, r;
    cin >> l >> r;
    int res = get(l, r);
    assert(res<=get2(l, r));
    cout << res << "\n";
  }

}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Runtime error 25 ms 9948 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 328 ms 109032 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Runtime error 25 ms 9948 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -