oj.uz

Submission #536384

# Submission time Handle Problem Language Result Execution time Memory
536384 2022-03-13T07:07:56 Z cig32 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 24540 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;
  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) {
      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 {

    //}
  }
}

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:85: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]
   85 |         if(s[i].size() < Q) continue;
      |            ~~~~~~~~~~~~^~~
selling_rna.cpp:86: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]
   86 |         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 468 KB Output is correct
2 Correct 1 ms 484 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 476 KB Output is correct
6 Correct 1 ms 484 KB Output is correct
7 Correct 1 ms 468 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 22300 KB Output is correct
2 Correct 192 ms 22728 KB Output is correct
3 Correct 72 ms 22348 KB Output is correct
4 Correct 87 ms 22500 KB Output is correct
5 Correct 39 ms 14280 KB Output is correct
6 Correct 43 ms 14452 KB Output is correct
7 Correct 166 ms 19404 KB Output is correct
8 Correct 61 ms 24540 KB Output is correct
9 Correct 74 ms 24324 KB Output is correct
10 Correct 380 ms 21864 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1580 ms 5364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 484 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 476 KB Output is correct
6 Correct 1 ms 484 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 59 ms 22300 KB Output is correct
9 Correct 192 ms 22728 KB Output is correct
10 Correct 72 ms 22348 KB Output is correct
11 Correct 87 ms 22500 KB Output is correct
12 Correct 39 ms 14280 KB Output is correct
13 Correct 43 ms 14452 KB Output is correct
14 Correct 166 ms 19404 KB Output is correct
15 Correct 61 ms 24540 KB Output is correct
16 Correct 74 ms 24324 KB Output is correct
17 Correct 380 ms 21864 KB Output is correct
18 Execution timed out 1580 ms 5364 KB Time limit exceeded
19 Halted 0 ms 0 KB -