Submission #1153020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153020		tuongll	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	155 ms	173608 KiB

selling_rna

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <ctime>
#include <cassert>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <bitset>
#include <array>
#include <sstream>
#include <limits>
using ll = long long;
#define debug(x) cout << #x << " = " << x << '\n'
#define separator "===============================================\n"
#define all(a) a.begin(), a.end()
#define SZ(a) (int)(a).size()
using namespace std;
const int mxn = 2e6 + 3;
const ll  mod = 1e9 + 7;
const int inf32 = 2e9;
const ll  inf64 = 4e18;
int id[mxn][4], m;
int id_rev[mxn][4], m_rev;
pair<int, int> T[mxn];
vector<int> T_rev[mxn];
int C[256];
void solve(){
  C['A'] = 0, C['U'] = 1, C['G'] = 2, C['C'] = 3;
  int n, q; cin >> n >> q;
  vector<string> s(n + 1);
  for (int i = 1; i <= n; ++i)
    cin >> s[i];
  sort(all(s));

  memset(id, -1, sizeof id);
  memset(id_rev, -1, sizeof id_rev);

  for (int i = 1; i <= n; ++i){
    int u = 0;
    for (char f : s[i]){
      int c = C[f];
      if (id[u][c] == -1) id[u][c] = ++m;
      u = id[u][c];
      if (T[u].first == 0) T[u].first = i;
      T[u].second = i;
    }

    reverse(all(s[i]));
    u = 0;
    for (char f : s[i]){
      int c = C[f];
      if (id_rev[u][c] == -1) id_rev[u][c] = ++m_rev;
      u = id_rev[u][c];
      T_rev[u].push_back(i);
    }
  }

  while(q--){
    string a, b;
    cin >> a >> b;
    reverse(all(b));

    int u = 0, res = 0;
    for (char f : a){
      int c = C[f];
      if (id[u][c] == -1){
        res = -1;
        break;
      }
      u = id[u][c];
    }
    int l, r; tie(l, r) = T[u];

    u = 0;
    for (char f : b){
      int c = C[f];
      if (id_rev[u][c] == -1){
        res = -1;
        break;
      }
      u = id_rev[u][c];
    }

    if (res == -1) cout << 0 << '\n';
    else cout << upper_bound(all(T_rev[u]), r) - upper_bound(all(T_rev[u]), l - 1) << '\n';
  }
}
int main(){
  auto start = chrono::steady_clock::now();
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  if (fopen("read.inp", "r")){
    freopen("read.inp", "r", stdin);
    freopen("write.out", "w", stdout);
  }
  int t = 1;
  // cin >> t;
  while(t--) solve();
  chrono::duration<double> elapsed {chrono::steady_clock::now() - start};
  cerr << "\n>> Runtime: " << elapsed.count() << "s\n";
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:100:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |     freopen("read.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:101:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     freopen("write.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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