oj.uz

Submission #1001575

# Submission time Handle Problem Language Result Execution time Memory
1001575 2024-06-19T06:03:35 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 6376 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 = 0;sz<min(L-i, (int)s[j].size());sz++) {
        if(S[sz+i] != s[j][sz])break;
        else nxt[i]=max(nxt[i], i+sz+1);
      }
    }
  }
  {
    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";
  }

}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 60 ms 3804 KB Output is correct
3 Correct 80 ms 5140 KB Output is correct
4 Correct 97 ms 5712 KB Output is correct
5 Correct 110 ms 5456 KB Output is correct
6 Correct 100 ms 5968 KB Output is correct
7 Correct 143 ms 5712 KB Output is correct
8 Correct 85 ms 5972 KB Output is correct
9 Correct 68 ms 5528 KB Output is correct
10 Correct 59 ms 4948 KB Output is correct
11 Correct 38 ms 6376 KB Output is correct
12 Correct 37 ms 5856 KB Output is correct
13 Correct 38 ms 5092 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 3256 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 2652 KB Output is correct
2 Correct 60 ms 3804 KB Output is correct
3 Correct 80 ms 5140 KB Output is correct
4 Correct 97 ms 5712 KB Output is correct
5 Correct 110 ms 5456 KB Output is correct
6 Correct 100 ms 5968 KB Output is correct
7 Correct 143 ms 5712 KB Output is correct
8 Correct 85 ms 5972 KB Output is correct
9 Correct 68 ms 5528 KB Output is correct
10 Correct 59 ms 4948 KB Output is correct
11 Correct 38 ms 6376 KB Output is correct
12 Correct 37 ms 5856 KB Output is correct
13 Correct 38 ms 5092 KB Output is correct
14 Execution timed out 2036 ms 3256 KB Time limit exceeded
15 Halted 0 ms 0 KB -