oj.uz

Submission #1001622

# Submission time Handle Problem Language Result Execution time Memory
1001622 2024-06-19T06:34:30 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 57128 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;
  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;

        }
      }
    }
  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 2652 KB Output is correct
2 Correct 66 ms 6680 KB Output is correct
3 Correct 86 ms 9044 KB Output is correct
4 Correct 112 ms 10580 KB Output is correct
5 Correct 110 ms 10064 KB Output is correct
6 Correct 98 ms 11148 KB Output is correct
7 Correct 127 ms 7608 KB Output is correct
8 Correct 96 ms 11604 KB Output is correct
9 Correct 74 ms 10880 KB Output is correct
10 Correct 57 ms 7120 KB Output is correct
11 Correct 43 ms 10992 KB Output is correct
12 Correct 35 ms 6628 KB Output is correct
13 Correct 40 ms 8944 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 53900 KB Output is correct
2 Correct 268 ms 55460 KB Output is correct
3 Correct 264 ms 53960 KB Output is correct
4 Correct 239 ms 52488 KB Output is correct
5 Correct 264 ms 52356 KB Output is correct
6 Correct 281 ms 55336 KB Output is correct
7 Correct 306 ms 55944 KB Output is correct
8 Correct 294 ms 55252 KB Output is correct
9 Correct 324 ms 55152 KB Output is correct
10 Correct 312 ms 55932 KB Output is correct
11 Correct 263 ms 54616 KB Output is correct
12 Correct 255 ms 53628 KB Output is correct
13 Correct 311 ms 57128 KB Output is correct
14 Correct 285 ms 56060 KB Output is correct
15 Correct 233 ms 51916 KB Output is correct
16 Correct 91 ms 35484 KB Output is correct
17 Correct 86 ms 45220 KB Output is correct
18 Correct 87 ms 45548 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 66 ms 6680 KB Output is correct
3 Correct 86 ms 9044 KB Output is correct
4 Correct 112 ms 10580 KB Output is correct
5 Correct 110 ms 10064 KB Output is correct
6 Correct 98 ms 11148 KB Output is correct
7 Correct 127 ms 7608 KB Output is correct
8 Correct 96 ms 11604 KB Output is correct
9 Correct 74 ms 10880 KB Output is correct
10 Correct 57 ms 7120 KB Output is correct
11 Correct 43 ms 10992 KB Output is correct
12 Correct 35 ms 6628 KB Output is correct
13 Correct 40 ms 8944 KB Output is correct
14 Correct 253 ms 53900 KB Output is correct
15 Correct 268 ms 55460 KB Output is correct
16 Correct 264 ms 53960 KB Output is correct
17 Correct 239 ms 52488 KB Output is correct
18 Correct 264 ms 52356 KB Output is correct
19 Correct 281 ms 55336 KB Output is correct
20 Correct 306 ms 55944 KB Output is correct
21 Correct 294 ms 55252 KB Output is correct
22 Correct 324 ms 55152 KB Output is correct
23 Correct 312 ms 55932 KB Output is correct
24 Correct 263 ms 54616 KB Output is correct
25 Correct 255 ms 53628 KB Output is correct
26 Correct 311 ms 57128 KB Output is correct
27 Correct 285 ms 56060 KB Output is correct
28 Correct 233 ms 51916 KB Output is correct
29 Correct 91 ms 35484 KB Output is correct
30 Correct 86 ms 45220 KB Output is correct
31 Correct 87 ms 45548 KB Output is correct
32 Execution timed out 2070 ms 36072 KB Time limit exceeded
33 Halted 0 ms 0 KB -