oj.uz

Submission #220163

# Submission time Handle Problem Language Result Execution time Memory
220163 2020-04-07T07:32:01 Z rama_pang Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 865 ms 598736 KB 
#include <bits/stdc++.h>
using namespace std;

void Transform(string &s) {
  for (auto &i : s) {
    if (i == 'A') i = '0';
    if (i == 'G') i = '1';
    if (i == 'C') i = '2';
    if (i == 'U') i = '3';
  }
}

class Trie {
 private:
  struct Node {
    int sz = 0;
    int nxt[4] = {-1, -1, -1, -1};
    Node() {}
  };

  vector<Node> trie = vector<Node>(1);

 public:
  Trie() {}
  vector<string> strings;

  void Insert(const string &s) {
    strings.emplace_back(s);
    int cur = 0;
    trie[cur].sz++;
    for (const auto &c : s) {
      if (trie[cur].nxt[c - '0'] == -1) {
        trie[cur].nxt[c - '0'] = trie.size();
        trie.emplace_back();
      }
      cur = trie[cur].nxt[c - '0'];
      trie[cur].sz++;
    }
  }

  int Count(const string &s) {
    int cur = 0;
    for (const auto &c : s) {
      if (cur == -1) break;
      cur = trie[cur].nxt[c - '0'];
    }
    if (cur == -1) {
      return 0;
    } else {
      return trie[cur].sz;
    }
  }

};

class SegmentTree {
 private:
  int sz;
  vector<Trie> tree;
  
 public:
  SegmentTree(const vector<string> &s) {
    sz = s.size();
    tree.resize(2 * sz);
    for (int i = 0; i < sz; i++) {
      tree[i + sz].Insert(s[i]);
    }
    for (int i = sz - 1; i > 0; i--) {
      for (const auto &j : tree[i * 2].strings) {
        tree[i].Insert(j);
      }
      for (const auto &j : tree[i * 2 + 1].strings) {
        tree[i].Insert(j);
      }
    }
  }

  int Query(int l, int r, const string &s) {
    int res = 0;
    for (l += sz, r += sz; l < r; l /= 2, r /= 2) {
      if (l & 1) res += tree[l++].Count(s);
      if (r & 1) res += tree[--r].Count(s);
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N, M;
  cin >> N >> M;

  vector<string> strings(N);
  for (int i = 0; i < N; i++) {
    cin >> strings[i];
    Transform(strings[i]);
  }

  sort(begin(strings), end(strings));
  for (int i = 0; i < N; i++) reverse(begin(strings[i]), end(strings[i]));
  SegmentTree seg(strings);
  for (int i = 0; i < N; i++) reverse(begin(strings[i]), end(strings[i]));

  for (int i = 0; i < M; i++) {
    string P, Q;
    cin >> P >> Q;

    Transform(P), Transform(Q);
    reverse(begin(Q), end(Q));

    int l = lower_bound(begin(strings), end(strings), P) - begin(strings);
    P.push_back('5');
    int r = lower_bound(begin(strings), end(strings), P) - begin(strings);
    P.pop_back();
    
    cout << seg.Query(l, r, Q) << "\n";
  }

  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 560572 KB Output is correct
2 Correct 675 ms 598736 KB Output is correct
3 Correct 399 ms 176412 KB Output is correct
4 Correct 410 ms 182260 KB Output is correct
5 Correct 478 ms 407364 KB Output is correct
6 Correct 481 ms 411908 KB Output is correct
7 Correct 274 ms 95684 KB Output is correct
8 Correct 554 ms 400220 KB Output is correct
9 Correct 511 ms 365272 KB Output is correct
10 Correct 458 ms 287120 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 45228 KB Output is correct
2 Correct 99 ms 30248 KB Output is correct
3 Correct 111 ms 37548 KB Output is correct
4 Correct 91 ms 30508 KB Output is correct
5 Correct 98 ms 28760 KB Output is correct
6 Correct 116 ms 36848 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 612 ms 560572 KB Output is correct
9 Correct 675 ms 598736 KB Output is correct
10 Correct 399 ms 176412 KB Output is correct
11 Correct 410 ms 182260 KB Output is correct
12 Correct 478 ms 407364 KB Output is correct
13 Correct 481 ms 411908 KB Output is correct
14 Correct 274 ms 95684 KB Output is correct
15 Correct 554 ms 400220 KB Output is correct
16 Correct 511 ms 365272 KB Output is correct
17 Correct 458 ms 287120 KB Output is correct
18 Correct 127 ms 45228 KB Output is correct
19 Correct 99 ms 30248 KB Output is correct
20 Correct 111 ms 37548 KB Output is correct
21 Correct 91 ms 30508 KB Output is correct
22 Correct 98 ms 28760 KB Output is correct
23 Correct 116 ms 36848 KB Output is correct
24 Correct 731 ms 594328 KB Output is correct
25 Correct 762 ms 597248 KB Output is correct
26 Correct 699 ms 589512 KB Output is correct
27 Correct 503 ms 195532 KB Output is correct
28 Correct 865 ms 324856 KB Output is correct
29 Correct 514 ms 144168 KB Output is correct