Submission #542419

#	Time	Username	Problem	Language	Result	Execution time	Memory
542419		cadmiumsky	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	412 ms	198952 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

const int lenmax = 2e6 + 5, nmax = 1e5 + 5;
int n, q;
  

int encr[256], decr[256];

string pad;

struct Trie {
  Trie* v[4] = {0, 0, 0, 0};
  vector<int> list;
  int l, r;
  void insert(int *s, int val) {
    l = 0, r = 0;
    if(s[0] == -1) {
      list.push_back(val);
      return;
    }
    if(v[s[0]] == 0)
      v[s[0]] = new Trie;
    v[s[0]]->insert(s + 1, val);
    return;
  }
  void construct(vector<int>& preord) {
    l = preord.size();
    for(auto x : list)
      preord.push_back(x);
    for(int i = 0; i < 4; i++) {
      if(v[i] != 0)
        v[i]->construct(preord);
    }
    r = preord.size() - 1;
  }
  pair<int,int> query(int *s) {
    if(s[0] == -1) {
      return {l, r};
    }
    if(v[s[0]] == 0)
      return {-1, -1};
    return v[s[0]]->query(s + 1);
  }
} forw, back;
int s[lenmax];
static void init() {
  encr['A'] = 0;
  encr['C'] = 1;
  encr['G'] = 2;
  encr['U'] = 3;
  encr['\n'] = -1;
  decr[0] = 'A';
  decr[1] = 'C';
  decr[2] = 'G';
  decr[3] = 'U';
}

namespace AINT {
  int aint[nmax * 4];
  void add(int poz, int node = 1, int cl = 0, int cr = n - 1) {
    if(cl == cr) {
      aint[node]++;
      return;
    }
    int mid = cl + cr >> 1;
    if(poz <= mid)  
      add(poz, 2 * node, cl, mid);
    else
      add(poz, 2 * node + 1, mid + 1, cr);
    aint[node] = aint[node  * 2 + 1] + aint[node * 2];
  }
  int query(int l, int r, int node = 1, int cl = 0, int cr = n - 1) {
    if(cr < l || r < cl)
      return 0;
    if(l <= cl && cr <= r)
      return aint[node];
    int mid = cl + cr >> 1;
    return query(l, r, 2 * node, cl, mid) + query(l, r, 2 * node + 1, mid + 1, cr);
  }
}

int rez[nmax];
vector<tuple<int,int,int> > qs[nmax];
#define qs (qs + 1)

int main() {
  init();
  cin >> n >> q;
  cin.get();
  for(int i = 0, ptr = 0; i < n; ptr = 0, i++) {
    char ch;
    while((ch = cin.get()) != '\n') {
      s[ptr++] = encr[ch];
    }
    s[ptr] = -1;
    forw.insert(s, i);
    reverse(s, s + ptr);
    back.insert(s, i);
  }
  vector<int> fata, spate, inv;
  forw.construct(fata);
  back.construct(spate);
  assert(fata.size() == n);
  assert(spate.size() == n);
  inv.resize(spate.size());
  //for(auto x : fata)
    //cout << x << ' ';
  //cout << '\n';
  //for(auto x : spate)
    //cout << x << ' ';
  //cout << '\n';
  for(int i = 0; i < spate.size(); i++)
    inv[spate[i]] = i;
  for(int i = 0; i < fata.size(); i++)
    fata[i] = inv[fata[i]];
  //for(auto x : fata)
    //cout << x << ' ';
  //cout << '\n';
  for(int i = 1, ptr = 0, l1, r1, l2, r2; i <= q; ptr = 0, i++) {
    char ch;
    while(!isspace(ch = cin.get())) {
      s[ptr++] = encr[ch];
    }
    s[ptr] = -1;
    ptr = 0;
    tie(l1, r1) = forw.query(s);
    while(!isspace(ch = cin.get())) {
      s[ptr++] = encr[ch];
    }
    s[ptr] = -1;
    reverse(s, s + ptr);
    tie(l2, r2) = back.query(s);
    if(l1 >= 0 && l2 >= 0 && r1 >= 0 && r2 >= 0) {
      qs[l1 - 1].push_back({-i, l2, r2});
      qs[r1].push_back({i, l2, r2});
    }
    //cerr << l1 << ' ' << r1 << ' '<< l2 << ' ' << r2 << '\n';
  }
  for(int i = 0; i < fata.size(); i++) {
    AINT::add(fata[i]);
    for(auto [ind, l, r] : qs[i])
      rez[abs(ind)] += AINT::query(l, r) * (ind / abs(ind));
  }
  for(int i = 1; i <= q; i++)
    cout << rez[i] << '\n';
}

Compilation message (stderr)

selling_rna.cpp: In function 'void AINT::add(int, int, int, int)':
selling_rna.cpp:67:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
selling_rna.cpp: In function 'int AINT::query(int, int, int, int, int)':
selling_rna.cpp:79:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:95:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   95 |       s[ptr++] = encr[ch];
      |                       ^~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from selling_rna.cpp:1:
selling_rna.cpp:105:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |   assert(fata.size() == n);
      |          ~~~~~~~~~~~~^~~~
selling_rna.cpp:106:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |   assert(spate.size() == n);
      |          ~~~~~~~~~~~~~^~~~
selling_rna.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for(int i = 0; i < spate.size(); i++)
      |                  ~~^~~~~~~~~~~~~~
selling_rna.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |   for(int i = 0; i < fata.size(); i++)
      |                  ~~^~~~~~~~~~~~~
selling_rna.cpp:124:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  124 |       s[ptr++] = encr[ch];
      |                       ^~
selling_rna.cpp:130:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  130 |       s[ptr++] = encr[ch];
      |                       ^~
selling_rna.cpp:141:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |   for(int i = 0; i < fata.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
selling_rna.cpp:143:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  143 |     for(auto [ind, l, r] : qs[i])
      |              ^

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