oj.uz

Submission #1001612

# Submission time Handle Problem Language Result Execution time Memory
1001612 2024-06-19T06:31:39 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 321 ms 71712 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;
  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 1628 KB Output is correct
2 Correct 152 ms 18728 KB Output is correct
3 Correct 178 ms 19404 KB Output is correct
4 Correct 269 ms 26176 KB Output is correct
5 Correct 238 ms 23412 KB Output is correct
6 Correct 316 ms 30208 KB Output is correct
7 Correct 155 ms 5632 KB Output is correct
8 Correct 321 ms 33844 KB Output is correct
9 Correct 267 ms 29824 KB Output is correct
10 Correct 87 ms 11036 KB Output is correct
11 Correct 51 ms 10100 KB Output is correct
12 Correct 49 ms 5612 KB Output is correct
13 Correct 50 ms 8124 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 71712 KB Output isn't correct
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 152 ms 18728 KB Output is correct
3 Correct 178 ms 19404 KB Output is correct
4 Correct 269 ms 26176 KB Output is correct
5 Correct 238 ms 23412 KB Output is correct
6 Correct 316 ms 30208 KB Output is correct
7 Correct 155 ms 5632 KB Output is correct
8 Correct 321 ms 33844 KB Output is correct
9 Correct 267 ms 29824 KB Output is correct
10 Correct 87 ms 11036 KB Output is correct
11 Correct 51 ms 10100 KB Output is correct
12 Correct 49 ms 5612 KB Output is correct
13 Correct 50 ms 8124 KB Output is correct
14 Incorrect 99 ms 71712 KB Output isn't correct
15 Halted 0 ms 0 KB -