oj.uz

Submission #1001607

# Submission time Handle Problem Language Result Execution time Memory
1001607 2024-06-19T06:29:42 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 340708 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;
      }
    }
  }
  {
    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;

      }
    }
  }
  if(L <= 500) {
    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 1880 KB Output is correct
2 Correct 139 ms 20820 KB Output is correct
3 Correct 154 ms 21836 KB Output is correct
4 Correct 222 ms 28736 KB Output is correct
5 Correct 209 ms 25892 KB Output is correct
6 Correct 238 ms 32852 KB Output is correct
7 Correct 162 ms 8364 KB Output is correct
8 Correct 277 ms 34472 KB Output is correct
9 Correct 193 ms 29780 KB Output is correct
10 Correct 77 ms 11096 KB Output is correct
11 Correct 46 ms 9964 KB Output is correct
12 Correct 43 ms 5608 KB Output is correct
13 Correct 46 ms 7920 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2019 ms 340708 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 1880 KB Output is correct
2 Correct 139 ms 20820 KB Output is correct
3 Correct 154 ms 21836 KB Output is correct
4 Correct 222 ms 28736 KB Output is correct
5 Correct 209 ms 25892 KB Output is correct
6 Correct 238 ms 32852 KB Output is correct
7 Correct 162 ms 8364 KB Output is correct
8 Correct 277 ms 34472 KB Output is correct
9 Correct 193 ms 29780 KB Output is correct
10 Correct 77 ms 11096 KB Output is correct
11 Correct 46 ms 9964 KB Output is correct
12 Correct 43 ms 5608 KB Output is correct
13 Correct 46 ms 7920 KB Output is correct
14 Execution timed out 2019 ms 340708 KB Time limit exceeded
15 Halted 0 ms 0 KB -