Submission #1001696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001696		vjudge1	Dabbeh (INOI20_dabbeh)	C++17	100 / 100	540 ms	63144 KiB

Main

#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;
  long long ans=1;
  if(nxt[at] >= r)return 1;
  for(int i = LG-1;i>=0;i--) {
    if(nxt[up[at][i]] < r) {
      at = up[at][i];
      ans+=(1ll<<i);
    }
  }
  if(nxt[up[at][0]] < r)return -1;
  return ans+1;
}
int get2(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] = min(L, 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;
      }
    }
    for(int i = L-1;i>=0;i--) {
      if(up[i][0] == 0)up[i][0] = i;

    }
    for(int i = L-1;i>=0;i--) {
      for(int j = 1;j<LG;j++)up[i][j] = up[up[i][j-1]][j-1];
    }
  }
  while(m--) {
    int l, r;
    cin >> l >> r;
    int res = get(l, r);
    cout << res << "\n";
  }

}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50