Submission #441073

#	Time	Username	Problem	Language	Result	Execution time	Memory
441073		codebuster_10	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	1221 ms	782188 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;
  }

}

Compilation message (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