Submission #536392

#	Time	Username	Problem	Language	Result	Execution time	Memory
536392		cig32	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	1137 ms	112632 KiB

selling_rna

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 120717661;
#define int long long
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { // read int128
  int x; cin >> x; return (ll)x;
}
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() { 
  for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD);
}
void solve(int tc) {
  int n, m;
  cin >> n >> m;
  string s[n];
  for(int i=0; i<n; i++) {
    cin >> s[i];
  }
  sort(s, s+n);
  const int wow = 137;
  vector<int> hash[n];
  for(int i=0; i<n; i++) {
    hash[i].resize(s[i].size());
    hash[i][0] = s[i][0] - 'A' + 1;
    for(int j=1; j<s[i].size(); j++) {
      hash[i][j] = (hash[i][j-1] * wow + s[i][j] - 'A' + 1) % MOD;
    }
  }
  #ifdef ONLINE_JUDGE
  const int maxQ = 2010000;
  #endif
  #ifndef ONLINE_JUDGE
  const int maxQ = 20000;
  #endif
  int pows[maxQ];
  pows[0] = 1;
  for(int i=1; i<maxQ; i++) pows[i] = (pows[i-1] * wow) % MOD;
  int sq = ceil(sqrt(n));
  unordered_map<int, int> freq[sq][2001];
  for(int i=0; i<n; i++) {
    for(int j=1; j<=min(2000ll, (int)s[i].size()); j++) {
      int z = (hash[i][hash[i].size() - 1] - (j == hash[i].size() ? 0 : hash[i][hash[i].size() - j - 1] * pows[j]) + MOD * pows[j]) % MOD;
      freq[i / sq][j][z]++;
    }
  }
  while(m--) {
    string p, q;
    cin >> p >> q;
    int P = p.size(), Q = q.size();
    int lb = 0, rb = n - 1;
    int L, R;
    while(lb < rb) {
      int mid = (lb + rb) >> 1;
      if(s[mid].substr(0, P) >= p) rb = mid;
      else lb = mid + 1;
    }
    int lb2 = 0, rb2 = n - 1;
    while(lb2 < rb2) {
      int mid = (lb2 + rb2 + 1) >> 1;
      if(s[mid].substr(0, P) <= p) lb2 = mid;
      else rb2 = mid - 1;
    }
    if(s[lb].substr(0, P) == p) {
      L = lb, R = lb2;
    }
    else {
      cout << "0\n"; continue;
    }
    if(Q > 2000 || L / sq == R / sq) {
      int rhs = 0;
      for(int i=0; i<Q; i++) rhs = (rhs * wow + q[i] - 'A' + 1) % MOD;
      int ans = 0;
      for(int i=L; i<=R; i++) {
        if(s[i].size() < Q) continue;
        int lhs = (hash[i][hash[i].size() - 1] - (Q == hash[i].size() ? 0 : hash[i][hash[i].size() - Q - 1] * pows[Q]) + MOD * pows[Q]) % MOD;
        ans += (lhs == rhs);
        //cout << s[i].substr(s[i].size() - Q, Q) << " " << lhs << " vs " << q << " " << rhs << "\n";
      }
      cout << ans << "\n"; continue;
    }
    else {
      int rhs = 0;
      for(int i=0; i<Q; i++) rhs = (rhs * wow + q[i] - 'A' + 1) % MOD;
      int ans = 0;
      while(L % sq != 0) {
        int i = L;
        if(s[i].size() < Q) {
          L++; continue;
        }
        int lhs = (hash[i][hash[i].size() - 1] - (Q == hash[i].size() ? 0 : hash[i][hash[i].size() - Q - 1] * pows[Q]) + MOD * pows[Q]) % MOD;
        ans += (lhs == rhs);
        L++;
      }
      while(R % sq != sq - 1) {
        int i = R;
        if(s[i].size() < Q) {
          R--; continue;
        }
        int lhs = (hash[i][hash[i].size() - 1] - (Q == hash[i].size() ? 0 : hash[i][hash[i].size() - Q - 1] * pows[Q]) + MOD * pows[Q]) % MOD;
        ans += (lhs == rhs);
        R--;
      }
      if(L <= R) {
        int lblock = L / sq;
        int rblock = R / sq;
        for(int i=lblock; i<=rblock; i++) {
          ans += freq[i][Q][rhs];
        }
      }
      cout << ans << "\n";
    }
  }
}

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 
/*
8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA

GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA
*/

Compilation message (stderr)

selling_rna.cpp: In function 'void solve(long long int)':
selling_rna.cpp:44:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int j=1; j<s[i].size(); j++) {
      |                  ~^~~~~~~~~~~~
selling_rna.cpp:61:49: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |       int z = (hash[i][hash[i].size() - 1] - (j == hash[i].size() ? 0 : hash[i][hash[i].size() - j - 1] * pows[j]) + MOD * pows[j]) % MOD;
      |                                               ~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:93:24: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   93 |         if(s[i].size() < Q) continue;
      |            ~~~~~~~~~~~~^~~
selling_rna.cpp:94:53: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         int lhs = (hash[i][hash[i].size() - 1] - (Q == hash[i].size() ? 0 : hash[i][hash[i].size() - Q - 1] * pows[Q]) + MOD * pows[Q]) % MOD;
      |                                                   ~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:106:24: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  106 |         if(s[i].size() < Q) {
      |            ~~~~~~~~~~~~^~~
selling_rna.cpp:109:53: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         int lhs = (hash[i][hash[i].size() - 1] - (Q == hash[i].size() ? 0 : hash[i][hash[i].size() - Q - 1] * pows[Q]) + MOD * pows[Q]) % MOD;
      |                                                   ~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:115:24: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  115 |         if(s[i].size() < Q) {
      |            ~~~~~~~~~~~~^~~
selling_rna.cpp:118:53: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         int lhs = (hash[i][hash[i].size() - 1] - (Q == hash[i].size() ? 0 : hash[i][hash[i].size() - Q - 1] * pows[Q]) + MOD * pows[Q]) % MOD;
      |                                                   ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40