oj.uz

Submission #1001573

# Submission time Handle Problem Language Result Execution time Memory
1001573 2024-06-19T06:00:07 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
0 / 100
 2000 ms 4876 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);

  for(int i = 0;i<L;i++) {
    for(int j = 0;j<n;j++) {
      for(int sz = 1;sz<=min(S.size(), s[j].size());sz++) {
        if(S.substr(i, sz) == s[j].substr(0, sz)) {
          nxt[i] = max(nxt[i], i+(int)sz);
        }
      }
    }
  }
  {
    vector<int> stk;
    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:65:24: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   65 |       for(int sz = 1;sz<=min(S.size(), s[j].size());sz++) {
      |                      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 790 ms 4876 KB Output is correct
3 Execution timed out 2004 ms 2392 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 2748 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 790 ms 4876 KB Output is correct
3 Execution timed out 2004 ms 2392 KB Time limit exceeded
4 Halted 0 ms 0 KB -