Submission #786047

#	Time	Username	Problem	Language	Result	Execution time	Memory
786047		tvladm2009	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	213 ms	201804 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int L = 2000000 + 7;
const int N = (int) 1e5 + 7;

int aib[L];

void add(int i, int x) {
  while (i < L) {
    aib[i] += x;
    i += i & -i;
  }
}

int get(int i) {
  int sol = 0;
  while (i >= 1) {
    sol += aib[i];
    i -= i & -i;
  }
  return sol;
}

int decode(char ch) {
  if (ch == 'A') return 0;
  if (ch == 'G') return 1;
  if (ch == 'C') return 2;
  if (ch == 'U') return 3;
  assert(false);
}

struct TrieNode {
  TrieNode* kids[4];
  int first;
  int last;
  vector<int> guys;

  TrieNode() {
    for (int i = 0; i < 4; i++) {
      kids[i] = nullptr;
    }
  }
};

void addToTrie(TrieNode* root, string s, int index) {
  TrieNode* current = root;
  for (auto &ch : s) {
    int decoded = decode(ch);
    if (!current->kids[decoded]) {
      current->kids[decoded] = new TrieNode;
    }
    current = current->kids[decoded];
  }
  current->guys.push_back(index);
}

void prepTrie(TrieNode* root, int inverse[]) {
  int index = 0;
  function<void(TrieNode*)> dfs = [&] (TrieNode* current) {
    current->first = ++index;
    for (auto &i : current->guys) {
      inverse[i] = index;
    }
    for (int j = 0; j < 4; j++) {
      if (current->kids[j]) {
        dfs(current->kids[j]);
      }
    }
    current->last = index;
  };
  dfs(root);
}

pair<int, int> getInterval(TrieNode* root, string s) {
  TrieNode* current = root;
  for (auto &ch : s) {
    int decoded = decode(ch);
    if (!current->kids[decoded]) {
      return {1, 0};
    }
    current = current->kids[decoded];
  }
  return {current->first, current->last};
}

TrieNode* root1 = new TrieNode;
TrieNode* root2 = new TrieNode;
int x[N];
int y[N];

struct BBox {
  int xmin;
  int ymin;
  int xmax;
  int ymax;
  int index;
};

struct Question {
  int x;
  int y;
  int coef;
  int index;
};

bool operator < (Question a, Question b) {
  return a.x < b.x;
}

bool cmp(int i, int j) {
  return x[i] < x[j];
}

int solPrint[N];

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  ///freopen("input", "r", stdin);

  int n, q;
  cin >> n >> q;

  vector<int> ord;
  for (int i = 1; i <= n; i++) {
    string s, revs;
    ord.push_back(i);
    cin >> s;
    revs = s;
    reverse(revs.begin(), revs.end());

    addToTrie(root1, s, i);
    addToTrie(root2, revs, i);
  }
  sort(ord.begin(), ord.end(), cmp);

  prepTrie(root1, x);
  prepTrie(root2, y);

  vector<Question> questions;

  for (int iq = 1; iq <= q; iq++) {
    string pref, suf;
    cin >> pref >> suf;

    reverse(suf.begin(), suf.end());

    auto xx = getInterval(root1, pref);
    auto yy = getInterval(root2, suf);


    if (xx.first > xx.second || yy.first > yy.second) {
      continue;
    }

    int x1 = xx.first, x2 = xx.second;
    int y1 = yy.first, y2 = yy.second;

    questions.push_back({x2, y2, +1, iq});
    questions.push_back({x2, y1 - 1, -1, iq});
    questions.push_back({x1 - 1, y2, -1, iq});
    questions.push_back({x1 - 1, y1 - 1, +1, iq});
  }

  sort(questions.begin(), questions.end());
  sort(ord.begin(), ord.end(), cmp);

  int it = 0;
  for (auto &question : questions) {
    while (it < n && x[ord[it]] <= question.x) {
      add(y[ord[it]], +1);
      it++;
    }
    int sol = get(question.y);
    sol *= question.coef;
    solPrint[question.index] += sol;
  }

  for (int iq = 1; iq <= q; iq++) {
    cout << solPrint[iq] << "\n";
  }


  return 0;
}

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