Submission #1106947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106947		zNatsumi	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	239 ms	193612 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

const int N = 1e5 + 5,
          INF = 1e9;

int n, m;
string s[N];

int id(char x){
  if(x == 'A') return 0;
  if(x == 'C') return 1;
  if(x == 'G') return 2;
  if(x == 'U') return 3;
}

struct Trie1{
  struct node{
    node* child[4];
    int l, r;
    node(): l(INF), r(-INF) {
      child[0] = child[1] = child[2] = child[3] = NULL;
    }
  };
  node* root;
  Trie1(): root(new node()){}

  void add(string &s, int idx){
    auto p = root;
    for(auto ch : s){
      int c = id(ch);
      if(!p->child[c]) p->child[c] = new node();
      p = p->child[c];
      p->l = min(p->l, idx);
      p->r = max(p->r, idx);
    }
  }
  ii query(string &s){
    auto p = root;
    for(auto ch : s){
      int c = id(ch);
      if(!p->child[c]) return {-1, -1};
      p = p->child[c];
    }
    return {p->l, p->r};
  }
} d1;

struct Trie2{
  struct node{
    node* child[4];
    vector<int> pos;
    node(){
      child[0] = child[1] = child[2] = child[3] = NULL;
    }
  };
  node* root;
  Trie2(): root(new node()) {}

  void add(string &s, int idx){
    auto p = root;
    for(auto ch : s){
      int c = id(ch);
      if(!p->child[c]) p->child[c] = new node();
      p = p->child[c];
      p->pos.push_back(idx);
    }
  }
  int query(string &s, int l, int r){
    auto p = root;
    for(auto ch : s){
      int c = id(ch);
      if(!p->child[c]) return 0;
      p = p->child[c];
    }
    int tl = lower_bound(p->pos.begin(), p->pos.end(), l) - p->pos.begin(),
        tr = upper_bound(p->pos.begin(), p->pos.end(), r) - p->pos.begin() - 1;
    return tr - tl + 1;
  }
} d2;

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> s[i];

  sort(s + 1, s + n + 1);
  for(int i = 1; i <= n; i++){
    d1.add(s[i], i);
    reverse(s[i].begin(), s[i].end());
    d2.add(s[i], i);
  }

  while(m--){
    string p, q; cin >> p >> q;
    reverse(q.begin(), q.end());

    auto range = d1.query(p);
    if(range == make_pair(-1, -1)) cout << 0 << "\n";
    else{
      cout << d2.query(q, range.first, range.second) << "\n";
    }
  }


  return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int id(char)':
selling_rna.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

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