제출 #441075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
441075		codebuster_10	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	1128 ms	782264 KiB

selling_rna

#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;
  }

}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40