oj.uz

Submission #1001603

# Submission time Handle Problem Language Result Execution time Memory
1001603 2024-06-19T06:28:22 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 340732 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;

      }
    }
  }
  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 133 ms 18720 KB Output is correct
3 Correct 151 ms 21844 KB Output is correct
4 Correct 233 ms 28752 KB Output is correct
5 Correct 198 ms 25916 KB Output is correct
6 Correct 238 ms 32852 KB Output is correct
7 Correct 151 ms 8460 KB Output is correct
8 Correct 256 ms 34328 KB Output is correct
9 Correct 174 ms 29664 KB Output is correct
10 Correct 77 ms 11184 KB Output is correct
11 Correct 45 ms 9964 KB Output is correct
12 Correct 45 ms 5560 KB Output is correct
13 Correct 43 ms 7916 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 340732 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 133 ms 18720 KB Output is correct
3 Correct 151 ms 21844 KB Output is correct
4 Correct 233 ms 28752 KB Output is correct
5 Correct 198 ms 25916 KB Output is correct
6 Correct 238 ms 32852 KB Output is correct
7 Correct 151 ms 8460 KB Output is correct
8 Correct 256 ms 34328 KB Output is correct
9 Correct 174 ms 29664 KB Output is correct
10 Correct 77 ms 11184 KB Output is correct
11 Correct 45 ms 9964 KB Output is correct
12 Correct 45 ms 5560 KB Output is correct
13 Correct 43 ms 7916 KB Output is correct
14 Execution timed out 2063 ms 340732 KB Time limit exceeded
15 Halted 0 ms 0 KB -