oj.uz

Submission #1001609

# Submission time Handle Problem Language Result Execution time Memory
1001609 2024-06-19T06:30:55 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 252 ms 77700 KB 
#include <bits/stdc++.h>
using namespace std;
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;
  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);
  map<long long, bool> 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][hss.get(1, j+1)]=1;
    }
  }
  if(L<= 500) {
  for(int i = 0;i<L;i++) {
    nxt[i]=i;
    int lo = 1, hi = L-i;
    while(lo <= hi) {
      int mid = (lo+hi)/2;
      if(mp[mid][hs.get(i+1, i+mid)]) {
        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;

        }
      }
    }
  while(m--) {
    int l, r;
    cin >> l >> r;
    int res = get(l, r);
    cout << res << "\n";
  }

}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 124 ms 18736 KB Output is correct
3 Correct 136 ms 20304 KB Output is correct
4 Correct 227 ms 27216 KB Output is correct
5 Correct 194 ms 24424 KB Output is correct
6 Correct 252 ms 31252 KB Output is correct
7 Correct 140 ms 6656 KB Output is correct
8 Correct 231 ms 32848 KB Output is correct
9 Correct 186 ms 28240 KB Output is correct
10 Correct 74 ms 9616 KB Output is correct
11 Correct 66 ms 10476 KB Output is correct
12 Correct 39 ms 6376 KB Output is correct
13 Correct 48 ms 7408 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 77700 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 1624 KB Output is correct
2 Correct 124 ms 18736 KB Output is correct
3 Correct 136 ms 20304 KB Output is correct
4 Correct 227 ms 27216 KB Output is correct
5 Correct 194 ms 24424 KB Output is correct
6 Correct 252 ms 31252 KB Output is correct
7 Correct 140 ms 6656 KB Output is correct
8 Correct 231 ms 32848 KB Output is correct
9 Correct 186 ms 28240 KB Output is correct
10 Correct 74 ms 9616 KB Output is correct
11 Correct 66 ms 10476 KB Output is correct
12 Correct 39 ms 6376 KB Output is correct
13 Correct 48 ms 7408 KB Output is correct
14 Runtime error 82 ms 77700 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -