oj.uz

Submission #1001608

# Submission time Handle Problem Language Result Execution time Memory
1001608 2024-06-19T06:30:14 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 302220 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;
    }
  }
  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;
      }
    }
  }
  if(L <= 500) {
    {
      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 1628 KB Output is correct
2 Correct 145 ms 18772 KB Output is correct
3 Correct 138 ms 20308 KB Output is correct
4 Correct 205 ms 27220 KB Output is correct
5 Correct 199 ms 24656 KB Output is correct
6 Correct 228 ms 31060 KB Output is correct
7 Correct 162 ms 6652 KB Output is correct
8 Correct 229 ms 32848 KB Output is correct
9 Correct 157 ms 28240 KB Output is correct
10 Correct 66 ms 9644 KB Output is correct
11 Correct 47 ms 10636 KB Output is correct
12 Correct 40 ms 5348 KB Output is correct
13 Correct 37 ms 7408 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2001 ms 302220 KB Time limit exceeded
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 Correct 145 ms 18772 KB Output is correct
3 Correct 138 ms 20308 KB Output is correct
4 Correct 205 ms 27220 KB Output is correct
5 Correct 199 ms 24656 KB Output is correct
6 Correct 228 ms 31060 KB Output is correct
7 Correct 162 ms 6652 KB Output is correct
8 Correct 229 ms 32848 KB Output is correct
9 Correct 157 ms 28240 KB Output is correct
10 Correct 66 ms 9644 KB Output is correct
11 Correct 47 ms 10636 KB Output is correct
12 Correct 40 ms 5348 KB Output is correct
13 Correct 37 ms 7408 KB Output is correct
14 Execution timed out 2001 ms 302220 KB Time limit exceeded
15 Halted 0 ms 0 KB -