Submission #372508

#	Time	Username	Problem	Language	Result	Execution time	Memory
372508		ivan_tudor	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	305 ms	196904 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
struct Trie{
  int st, fn;
  vector<int> fnl;
  Trie *child[4];
  Trie(){
    st = fn = 0;
    fnl.clear();
    child[0] = child[1] = child[2] = child[3] = NULL;
  }
};
int getson(char c){
  if(c == 'A')
    return 0;
  if(c == 'C')
    return 1;
  if(c == 'G')
    return 2;
  return 3;
}
void ins(Trie* nod, const string &s, int i,int id){
  if(i == s.size() ){
    nod->fnl.push_back(id);
    return;
  }
  int nxt = getson(s[i]);
  if(nod->child[nxt] == NULL)
    nod->child[nxt] = new Trie;
  ins(nod->child[nxt], s, i+1, id);
}
void dfs(Trie* nod, int &t, int inv[]){ // t sta mereu pe primul neluat
  nod->st = t;
  for(auto x: nod->fnl){
    inv[x] = t++;
  }
  for(int kid = 0; kid < 4; kid++)
    if(nod->child[kid] != NULL)
      dfs(nod->child[kid], t, inv);
  nod->fn = t - 1;
}
Trie* findnode(Trie* nod, int i, const string &s){
  if(nod == NULL)
    return NULL;
  if(i == s.size())
    return nod;
  int nxt = getson(s[i]);
  return findnode(nod->child[nxt], i+1, s);
}
Trie *rootP = new Trie, *rootS = new Trie;
const int N = 100005;
int invP[N], invS[N];
struct eveniment{
  int t;
  int ys, ye;
  int tip;
  int id;
};
vector<eveniment> ev;
int ans[N];
bool cmpev(eveniment a, eveniment b){
  if(a.t == b.t)
    return a.tip < b.tip;
  return a.t < b.t;
}


int aib[N];
void update(int poz, int val){
  for(int i = poz; i <N; i+= i &(-i))
    aib[i] += val;
}
int query(int poz){
  int ans = 0;
  for(int i = poz; i>0; i-= i&(-i))
    ans += aib[i];
  return ans;
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, m;
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    string s;
    cin>>s;
    ins(rootP, s, 0, i);
    reverse(s.begin(), s.end());
    ins(rootS, s, 0, i);
  }
  int t = 1;
  dfs(rootP, t, invP);
  t = 1;
  dfs(rootS, t, invS);
  for(int i= 1; i<=n;i++){
    eveniment upd = {invP[i], invS[i], invS[i], 0, 0};
    ev.push_back(upd);
  }
  for(int i = 1; i<=m;i++){
    string p, q;
    cin>>p>>q;
    reverse(q.begin(), q.end());
    Trie *pref, *suf;
    pref = findnode(rootP, 0, p);
    suf = findnode(rootS, 0, q);
    if(pref == NULL || suf == NULL){
      ans[i] = 0;
      continue;
    }
    eveniment firstupd  = {pref->st, suf->st, suf->fn, -1, i};
    ev.push_back(firstupd);
    eveniment secondupd = {pref->fn, suf->st, suf->fn, 1, i};
    ev.push_back(secondupd);
  }
  sort(ev.begin(), ev.end(), cmpev);
  for(auto e:ev){
    if(e.tip == 0){
      update(e.ys, 1);
    }
    else{
      ans[e.id] += (query(e.ye) - query(e.ys - 1)) * e.tip;
    }
  }
  for(int i=1;i<=m;i++){
    cout<<ans[i]<<"\n";
  }
  return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void ins(Trie*, const string&, int, int)':
selling_rna.cpp:23:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   if(i == s.size() ){
      |      ~~^~~~~~~~~~~
selling_rna.cpp: In function 'Trie* findnode(Trie*, int, const string&)':
selling_rna.cpp:45:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   if(i == s.size())
      |      ~~^~~~~~~~~~~

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