Submission #1106297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106297		VinhLuu	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	259 ms	275720 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40