Submission #1001592

#TimeUsernameProblemLanguageResultExecution timeMemory
1001592vjudge1Dabbeh (INOI20_dabbeh)C++17
0 / 100
2036 ms302764 KiB
#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]; for(int i = 0;i<n;i++) { hsg::PolyHash hss(s[i]); for(int j = 0 ;j<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 (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int j = 0 ;j<s[i].size();j++) {
      |                    ~^~~~~~~~~~~~
Main.cpp:62:7: warning: unused variable 'idx' [-Wunused-variable]
   62 |   int idx[L];
      |       ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...