oj.uz

Submission #536392

# Submission time Handle Problem Language Result Execution time Memory
536392 2022-03-13T07:24:06 Z cig32 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1137 ms 112632 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 95056 KB Output is correct
2 Correct 394 ms 112632 KB Output is correct
3 Correct 124 ms 41000 KB Output is correct
4 Correct 128 ms 43340 KB Output is correct
5 Correct 258 ms 74024 KB Output is correct
6 Correct 239 ms 75084 KB Output is correct
7 Correct 101 ms 25252 KB Output is correct
8 Correct 282 ms 83204 KB Output is correct
9 Correct 227 ms 69336 KB Output is correct
10 Correct 172 ms 54012 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 29700 KB Output is correct
2 Correct 107 ms 23264 KB Output is correct
3 Correct 164 ms 27212 KB Output is correct
4 Correct 97 ms 24024 KB Output is correct
5 Correct 95 ms 23220 KB Output is correct
6 Correct 129 ms 26888 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 330 ms 95056 KB Output is correct
9 Correct 394 ms 112632 KB Output is correct
10 Correct 124 ms 41000 KB Output is correct
11 Correct 128 ms 43340 KB Output is correct
12 Correct 258 ms 74024 KB Output is correct
13 Correct 239 ms 75084 KB Output is correct
14 Correct 101 ms 25252 KB Output is correct
15 Correct 282 ms 83204 KB Output is correct
16 Correct 227 ms 69336 KB Output is correct
17 Correct 172 ms 54012 KB Output is correct
18 Correct 143 ms 29700 KB Output is correct
19 Correct 107 ms 23264 KB Output is correct
20 Correct 164 ms 27212 KB Output is correct
21 Correct 97 ms 24024 KB Output is correct
22 Correct 95 ms 23220 KB Output is correct
23 Correct 129 ms 26888 KB Output is correct
24 Correct 428 ms 104804 KB Output is correct
25 Correct 615 ms 105060 KB Output is correct
26 Correct 407 ms 104152 KB Output is correct
27 Correct 198 ms 46152 KB Output is correct
28 Correct 1137 ms 75732 KB Output is correct
29 Correct 445 ms 54252 KB Output is correct