oj.uz

Submission #372508

# Submission time Handle Problem Language Result Execution time Memory
372508 2021-02-28T14:04:27 Z ivan_tudor Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 305 ms 196904 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 155420 KB Output is correct
2 Correct 219 ms 151208 KB Output is correct
3 Correct 228 ms 157352 KB Output is correct
4 Correct 215 ms 149804 KB Output is correct
5 Correct 299 ms 194244 KB Output is correct
6 Correct 305 ms 196904 KB Output is correct
7 Correct 46 ms 6712 KB Output is correct
8 Correct 196 ms 118824 KB Output is correct
9 Correct 181 ms 100648 KB Output is correct
10 Correct 138 ms 95400 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6780 KB Output is correct
2 Correct 32 ms 4456 KB Output is correct
3 Correct 43 ms 4720 KB Output is correct
4 Correct 39 ms 4072 KB Output is correct
5 Correct 33 ms 4480 KB Output is correct
6 Correct 42 ms 4732 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 236 ms 155420 KB Output is correct
9 Correct 219 ms 151208 KB Output is correct
10 Correct 228 ms 157352 KB Output is correct
11 Correct 215 ms 149804 KB Output is correct
12 Correct 299 ms 194244 KB Output is correct
13 Correct 305 ms 196904 KB Output is correct
14 Correct 46 ms 6712 KB Output is correct
15 Correct 196 ms 118824 KB Output is correct
16 Correct 181 ms 100648 KB Output is correct
17 Correct 138 ms 95400 KB Output is correct
18 Correct 46 ms 6780 KB Output is correct
19 Correct 32 ms 4456 KB Output is correct
20 Correct 43 ms 4720 KB Output is correct
21 Correct 39 ms 4072 KB Output is correct
22 Correct 33 ms 4480 KB Output is correct
23 Correct 42 ms 4732 KB Output is correct
24 Correct 211 ms 132044 KB Output is correct
25 Correct 229 ms 133468 KB Output is correct
26 Correct 199 ms 130152 KB Output is correct
27 Correct 209 ms 130436 KB Output is correct
28 Correct 186 ms 33652 KB Output is correct
29 Correct 121 ms 15720 KB Output is correct