oj.uz

Submission #1001598

# Submission time Handle Problem Language Result Execution time Memory
1001598 2024-06-19T06:25:28 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 302216 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);
  int idx[L];
  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;
      }
    }
  }
  {
    for(int i = 0;i<L;i++) {
      int curmx = i;
      for(int j = 0;j<L;j++) {
        if(j <= nxt[i] and nxt[j] > nxt[curmx] and j >= i) {
          curmx = j;
        }
      }
      up[i][0] = curmx;
    }
  }
  while(m--) {
    int l, r;
    cin >> l >> r;
    int res = get(l, r);
    cout << res << "\n";
  }

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:62:7: warning: unused variable 'idx' [-Wunused-variable]
   62 |   int idx[L];
      |       ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 134 ms 18776 KB Output is correct
3 Correct 134 ms 19356 KB Output is correct
4 Correct 183 ms 26296 KB Output is correct
5 Correct 199 ms 25820 KB Output is correct
6 Correct 221 ms 32852 KB Output is correct
7 Correct 152 ms 8444 KB Output is correct
8 Correct 250 ms 34436 KB Output is correct
9 Correct 181 ms 29784 KB Output is correct
10 Correct 74 ms 11092 KB Output is correct
11 Correct 50 ms 9968 KB Output is correct
12 Correct 41 ms 5604 KB Output is correct
13 Correct 44 ms 7920 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 302216 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 134 ms 18776 KB Output is correct
3 Correct 134 ms 19356 KB Output is correct
4 Correct 183 ms 26296 KB Output is correct
5 Correct 199 ms 25820 KB Output is correct
6 Correct 221 ms 32852 KB Output is correct
7 Correct 152 ms 8444 KB Output is correct
8 Correct 250 ms 34436 KB Output is correct
9 Correct 181 ms 29784 KB Output is correct
10 Correct 74 ms 11092 KB Output is correct
11 Correct 50 ms 9968 KB Output is correct
12 Correct 41 ms 5604 KB Output is correct
13 Correct 44 ms 7920 KB Output is correct
14 Execution timed out 2064 ms 302216 KB Time limit exceeded
15 Halted 0 ms 0 KB -