oj.uz

Submission #441078

# Submission time Handle Problem Language Result Execution time Memory
441078 2021-07-04T05:43:53 Z codebuster_10 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1157 ms 782224 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int int64_t //be careful about this 
#define endl "\n"
#define f(i, a, b) for (int i = int(a); i < int(b); ++i)
 
#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
 
#define SZ(x) ((int)(x).size())
#define all(a) (a).begin(), (a).end()
#define allr(a) (a).rbegin(), (a).rend()
#define mem(a, b) memset(a, b, sizeof(a))
 
void setIO(string s = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // remove this when size of input is not fixed.
  cin.exceptions(cin.failbit);
  cout.precision(15);
  cout << fixed;
  if (SZ(s)) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
  }
}
 
template<const int ALPHABET>
struct prefix_tree {
 
  struct trie_node {
    int link[ALPHABET];
    vector<int> who;
 
    trie_node() {
      memset(link, -1, sizeof(link));
    }
  };
 
  vector<trie_node> trie;
 
  prefix_tree() {
    trie.emplace_back();
  }
 
  void create_node(int parent, int c) {
    trie.emplace_back();
  }
 
  int get_or_create_node(int current, int c) {
    if (trie[current].link[c] < 0) {
      trie[current].link[c] = trie.size();
      create_node(current, c);
    }
 
    return trie[current].link[c];
  }
 
  int insert_str(const string & str, const int & i) {
    int current = 0;
    for (char c: str) {
      current = get_or_create_node(current, c - 'A');
      trie[current].who.push_back(i);
    }
    return current;
  }
 
  ar<int,2> query(const string & str) {
    int current = 0;
    for (char c: str) {
      if (trie[current].link[c - 'A'] < 0) return ar<int,2> {-1,-1};
      current = trie[current].link[c - 'A'];
    }
    return ar<int,2> {trie[current].who.front(),trie[current].who.back()};
  }
 
  int query(const string & str, int L, int R) {
    int current = 0;
    for (char c: str) {
      if (trie[current].link[c - 'A'] < 0) return int(0);
      current = trie[current].link[c - 'A'];
    }
    return int(upper_bound(all(trie[current].who), R) - lower_bound(all(trie[current].who), L));
  }
};
 
prefix_tree<26> trie, reverse_trie;
 
signed main() {
  setIO();
  int n, q;
  cin >> n >> q;
  vt<string> s(n);
  for (auto & _s: s) cin >> _s;
  sort(all(s));
 
  f(i, 0, n) {
    trie.insert_str(s[i], i);
    reverse(all(s[i]));
    reverse_trie.insert_str(s[i], i);
  }
 
  while (q--) {
    string p, q;
    cin >> p >> q;
    auto [L, R] = trie.query(p);
    reverse(all(q));
    cout << reverse_trie.query(q, L, R) << endl;
  }
 
}

Compilation message

selling_rna.cpp: In function 'void setIO(std::string)':
selling_rna.cpp:31:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 750 ms 533428 KB Output is correct
2 Correct 735 ms 524560 KB Output is correct
3 Correct 715 ms 524816 KB Output is correct
4 Correct 698 ms 524956 KB Output is correct
5 Correct 1157 ms 782136 KB Output is correct
6 Correct 1146 ms 782224 KB Output is correct
7 Correct 94 ms 34348 KB Output is correct
8 Correct 747 ms 456384 KB Output is correct
9 Correct 639 ms 443620 KB Output is correct
10 Correct 606 ms 419496 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4088 KB Output is correct
2 Correct 28 ms 5044 KB Output is correct
3 Correct 31 ms 4328 KB Output is correct
4 Correct 23 ms 3348 KB Output is correct
5 Correct 28 ms 4616 KB Output is correct
6 Correct 33 ms 4704 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 750 ms 533428 KB Output is correct
9 Correct 735 ms 524560 KB Output is correct
10 Correct 715 ms 524816 KB Output is correct
11 Correct 698 ms 524956 KB Output is correct
12 Correct 1157 ms 782136 KB Output is correct
13 Correct 1146 ms 782224 KB Output is correct
14 Correct 94 ms 34348 KB Output is correct
15 Correct 747 ms 456384 KB Output is correct
16 Correct 639 ms 443620 KB Output is correct
17 Correct 606 ms 419496 KB Output is correct
18 Correct 31 ms 4088 KB Output is correct
19 Correct 28 ms 5044 KB Output is correct
20 Correct 31 ms 4328 KB Output is correct
21 Correct 23 ms 3348 KB Output is correct
22 Correct 28 ms 4616 KB Output is correct
23 Correct 33 ms 4704 KB Output is correct
24 Correct 701 ms 526520 KB Output is correct
25 Correct 710 ms 526536 KB Output is correct
26 Correct 698 ms 526532 KB Output is correct
27 Correct 692 ms 527268 KB Output is correct
28 Correct 298 ms 96684 KB Output is correct
29 Correct 105 ms 22416 KB Output is correct