Submission #362029

#	Time	Username	Problem	Language	Result	Execution time	Memory
362029		AlexLuchianov	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	313 ms	158572 KiB

selling_rna

#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <algorithm>

using ll = long long;

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const sigma = 4;

struct Trie{
  std::vector<int> ids;
  Trie* p[sigma];
  Trie() {
    for(int i = 0; i < sigma; i++)
      p[i] = nullptr;
  }
};

int const bigsigma = 256;
char mp[1 + bigsigma];

void _add(Trie* &root, std::string &s, int pos, int id) {
  if(root == nullptr)
    root = new Trie();

  if(s.size() == pos)
    root->ids.push_back(id);
  else 
    _add(root->p[mp[s[pos]]], s, pos + 1, id);
  
}

void dfs(Trie* &root, int target, std::vector<int> &parc, std::vector<int> &start, std::vector<int> &stop) {

  for(int h = 0; h < root->ids.size(); h++) {
    int id = root->ids[h];
    if(target < id) 
      start[id - 1 - target] = parc.size();
  }

  for(int h = 0; h < root->ids.size(); h++) {
    int id = root->ids[h];
    if(id <= target)
      parc.push_back(id);
  }
  for(int h = 0; h < sigma; h++)
    if(root->p[h] != nullptr)
      dfs(root->p[h], target, parc, start, stop);

  for(int h = 0; h < root->ids.size(); h++) {
    int id = root->ids[h];
    if(target < id) 
      stop[id - 1 - target] = parc.size() - 1;
  }
}

Trie *root = nullptr, *root2 = nullptr;

class FenwickTree{
private:
  int n;
  std::vector<int> aib;
public:
  FenwickTree(int n_) {
    n = n_;
    aib.resize(1 + n);
  }
  void update(int pos, int val) {
    if(pos == 0) {
      aib[0] += val;
      return ;
    }
    for(int x = pos; x <= n; x += (x ^ (x & (x - 1))))
      aib[x] += val;
  }
  int query(int pos) {
    if(pos < 0)
      return 0;
    int result = 0;
    for(int x = pos; 0 < x; x = (x & (x - 1)))
      result += aib[x];
    return result + aib[0];
  }
};
int const nmax = 100000;

int sol[1 + nmax];

int main() {
  mp['A'] = 0;
  mp['G'] = 1;
  mp['C'] = 2;
  mp['U'] = 3;

  int n, q;
  std::cin >> n >> q;
  
  for(int i = 1; i <= n; i++) { 
    std::string s;
    std::cin >> s;
    _add(root, s, 0, i);
    std::reverse(s.begin(), s.end());
    _add(root2, s, 0, i);
  }
  for(int i = 1;i <= q; i++) {
    std::string p, q;
    std::cin >> p >> q;
    std::reverse(q.begin(), q.end());
    _add(root, p, 0, n + i);
    _add(root2, q, 0, n + i);
  }

  std::vector<int> parc1, start1(q), stop1(q);
  std::vector<int> parc2, start2(q), stop2(q);
  std::vector<int> pos1(n + 1);
  
  dfs(root, n, parc1, start1, stop1);
  dfs(root2, n, parc2, start2, stop2);
  

  for(int i = 0; i < n; i++)
    pos1[parc1[i]] = i;
  
  std::vector<std::vector<std::pair<int,int>>> events(1 + n);
  
  for(int i = 0; i < q; i++) {
    if(start2[i] <= stop2[i]) {
      events[stop2[i]].push_back({i, 1});
      if(0 < start2[i]) 
        events[start2[i] - 1].push_back({i, -1});
    }
  }

  FenwickTree aib(1 + n);
  
  for(int i = 0; i < n; i++) {
    aib.update(pos1[parc2[i]], 1);
    for(int h = 0; h < events[i].size(); h++) {
      int id = events[i][h].first;
      sol[id] += events[i][h].second * (aib.query(stop1[id]) - aib.query(start1[id] - 1));
    }
  }
  
  for(int i = 0; i < q; i++)
    std::cout << sol[i] << '\n';
  return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void _add(Trie*&, std::string&, int, int)':
selling_rna.cpp:30:15: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |   if(s.size() == pos)
      |      ~~~~~~~~~^~~~~~
selling_rna.cpp:33:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   33 |     _add(root->p[mp[s[pos]]], s, pos + 1, id);
      |                           ^
selling_rna.cpp:33:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   33 |     _add(root->p[mp[s[pos]]], s, pos + 1, id);
      |                  ~~~~~~~~~^
selling_rna.cpp: In function 'void dfs(Trie*&, int, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
selling_rna.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int h = 0; h < root->ids.size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~~~
selling_rna.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int h = 0; h < root->ids.size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~~~
selling_rna.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int h = 0; h < root->ids.size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int h = 0; h < events[i].size(); h++) {
      |                    ~~^~~~~~~~~~~~~~~~~~

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