oj.uz

Submission #1106297

# Submission time Handle Problem Language Result Execution time Memory
1106297 2024-10-29T18:29:27 Z VinhLuu Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 259 ms 275720 KB 
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second

using namespace std;

typedef pair<int,int> pii;
const int N = 2e5 + 5;
//const int M = 2e6 + 5;
const int oo = 1e9;

int n, m;
string s[N], a[N], b[N];

char change(char c){
  if(c == 'A') return '1';
  if(c == 'C') return '2';
  if(c == 'G') return '3';
  return '4';
}

struct trie{
  trie* child[8];
  vector<int> w;
  trie(){
    for(int i = 1; i <= 4; i ++) child[i] = NULL;
    w.clear();
  }
};

trie* root;

void add(string &x,int id){
  trie* p = root;
  for(auto i : x){
    int val = (i - '0');
    if(p -> child[val] == NULL) p -> child[val] = new trie();
    p = p -> child[val];
    p -> w.push_back(id);
  }
}

int query(string &x,int l,int r){
  trie* p = root;
  for(auto i : x){
    int val = (i - '0');
    if(p -> child[val] == NULL) return 0;
    p = p -> child[val];
  }

  auto v = upper_bound(p -> w.begin(), p -> w.end(), r);
  auto u = lower_bound(p -> w.begin(), p -> w.end(), l);
  if(v == p -> w.begin()) return 0;
  if(u == p -> w.end()) return 0;
  v--;
  int tu = u - p -> w.begin();
  int tv = v - p -> w.begin();
  if(tu <= tv) return tv - tu + 1;
  return 0;
}

struct tree{
  tree* child[8];

  int mx, mi;
  tree(){
    for(int i = 1; i <= 4; i ++) child[i] = NULL;
    mx = 0, mi = n + 1;
  }
};

tree* wr;

void update(string &x,int id){
  tree* p = wr;
  for(auto i : x){
    int val = (i - '0');
    if(p -> child[val] == NULL) p -> child[val] = new tree();
    p = p -> child[val];
    p -> mx = max(p -> mx, id);
    p -> mi = min(p -> mi, id);
  }
}

pair<int,int> get(string &x){
  tree* p = wr;
  for(auto i : x){
    int val = (i - '0');
    if(p -> child[val] == NULL) return {0, 0};
    p = p -> child[val];
  }
  return {p -> mi, p -> mx};
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  root = new trie();
  wr = new tree();

  cin >> n >> m;
  for(int i = 1; i <= n; i ++){
    cin >> s[i];
    for(int j = 0; j < s[i].size(); j ++){
      s[i][j] = change(s[i][j]);
    }
  }
  sort(s + 1, s + n + 1);

  for(int i = 1; i <= n; i ++){
    update(s[i], i);
    string hk = s[i];
    reverse(hk.begin(), hk.end());
    add(hk, i);
  }

  for(int i = 1; i <= m; i ++){
    cin >> a[i] >> b[i];
    for(int j = 0; j < a[i].size(); j ++) a[i][j] = change(a[i][j]);
    for(int j = 0; j < b[i].size(); j ++) b[i][j] = change(b[i][j]);
    pair<int,int> kq = get(a[i]);
    if(!kq.first){
      cout << 0 << "\n";
      continue;
    }
    reverse(b[i].begin(), b[i].end());
    cout << query(b[i], kq.first, kq.second) << "\n";
  }


}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int j = 0; j < s[i].size(); j ++){
      |                    ~~^~~~~~~~~~~~~
selling_rna.cpp:127:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int j = 0; j < a[i].size(); j ++) a[i][j] = change(a[i][j]);
      |                    ~~^~~~~~~~~~~~~
selling_rna.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int j = 0; j < b[i].size(); j ++) b[i][j] = change(b[i][j]);
      |                    ~~^~~~~~~~~~~~~
selling_rna.cpp:102:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:103:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19024 KB Output is correct
2 Correct 4 ms 19280 KB Output is correct
3 Correct 3 ms 19280 KB Output is correct
4 Correct 3 ms 19124 KB Output is correct
5 Correct 3 ms 19024 KB Output is correct
6 Correct 3 ms 19120 KB Output is correct
7 Correct 4 ms 19024 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 269896 KB Output is correct
2 Correct 245 ms 256464 KB Output is correct
3 Correct 165 ms 188228 KB Output is correct
4 Correct 154 ms 182600 KB Output is correct
5 Correct 242 ms 272012 KB Output is correct
6 Correct 250 ms 275720 KB Output is correct
7 Correct 57 ms 38996 KB Output is correct
8 Correct 188 ms 182280 KB Output is correct
9 Correct 166 ms 158536 KB Output is correct
10 Correct 146 ms 149880 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19916 KB Output is correct
2 Correct 17 ms 20296 KB Output is correct
3 Correct 21 ms 20016 KB Output is correct
4 Correct 15 ms 19904 KB Output is correct
5 Correct 17 ms 20376 KB Output is correct
6 Correct 20 ms 20216 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19024 KB Output is correct
2 Correct 4 ms 19280 KB Output is correct
3 Correct 3 ms 19280 KB Output is correct
4 Correct 3 ms 19124 KB Output is correct
5 Correct 3 ms 19024 KB Output is correct
6 Correct 3 ms 19120 KB Output is correct
7 Correct 4 ms 19024 KB Output is correct
8 Correct 242 ms 269896 KB Output is correct
9 Correct 245 ms 256464 KB Output is correct
10 Correct 165 ms 188228 KB Output is correct
11 Correct 154 ms 182600 KB Output is correct
12 Correct 242 ms 272012 KB Output is correct
13 Correct 250 ms 275720 KB Output is correct
14 Correct 57 ms 38996 KB Output is correct
15 Correct 188 ms 182280 KB Output is correct
16 Correct 166 ms 158536 KB Output is correct
17 Correct 146 ms 149880 KB Output is correct
18 Correct 21 ms 19916 KB Output is correct
19 Correct 17 ms 20296 KB Output is correct
20 Correct 21 ms 20016 KB Output is correct
21 Correct 15 ms 19904 KB Output is correct
22 Correct 17 ms 20376 KB Output is correct
23 Correct 20 ms 20216 KB Output is correct
24 Correct 230 ms 228936 KB Output is correct
25 Correct 259 ms 229408 KB Output is correct
26 Correct 217 ms 226376 KB Output is correct
27 Correct 158 ms 161620 KB Output is correct
28 Correct 131 ms 63560 KB Output is correct
29 Correct 58 ms 27720 KB Output is correct