Submission #1169379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169379		nhphuc	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	99 ms	83132 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

const int N = 400100;

int mp[257], id[N * 4][4], cnt[N * 4], timer = 0;

void init (){
    mp['A'] = 0;
    mp['C'] = 1;
    mp['G'] = 2;
    mp['U'] = 3;
    timer = 1;
    for (int i = 0; i < 4 * N; ++i){
        cnt[i] = 0;
        for (int j = 0; j < 4; ++j){
            id[i][j] = 0;
        }
    }
    return;
}

void ins (string &s, int i = 0, int cur = 1){
    ++cnt[cur];
    if (i == s.size()){
        return;
    }
    if (!id[cur][mp[s[i]]]){
        id[cur][mp[s[i]]] = ++timer;
    }
    ins(s, i + 1, id[cur][mp[s[i]]]);
    return;
}

int get (string &s, int i, int cur, bool pref, bool current){
    if (i == s.size() || cur == 0){
        return cnt[cur] * current;
    }
    int ans = 0, sum = 0;
    if (pref == true){
      for (int j = 0; j < 4; ++j){
          sum += cnt[id[cur][j]];
      }
      ans = cnt[cur] - sum;
      for (int j = 0; j < mp[s[i]]; ++j){
          ans += cnt[id[cur][j]];
      }
    }
    return ans + get(s, i + 1, id[cur][mp[s[i]]], pref, current);
}

int n, m, res[N];
string s[N], a[N], b[N];
vector<pair<int, int>> que[N];

int32_t main (){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    if (fopen ("test.inp", "r")){
        freopen ("test.inp", "r", stdin);
        freopen ("test.out", "w", stdout);
    }
    init();
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        cin >> s[i];
        ins(s[i]);
    }
    sort(s + 1, s + n + 1);
    for (int i = 1; i <= m; ++i){
        cin >> a[i] >> b[i];
        reverse(b[i].begin(), b[i].end());
        int l = get(a[i], 0, 1, true, false);
        int r = get(a[i], 0, 1, true, true);
        que[l].push_back({-1, i});
        que[r].push_back({1, i});
    }
    init();
    for (int i = 1; i <= n; ++i){
        reverse(s[i].begin(), s[i].end());
        ins(s[i]);
        for (auto [x, y] : que[i]){
            res[y] += x * get(b[y], 0, 1, false, true);
        }
    }
    for (int i = 1; i <= m; ++i){
        cout << res[i] << "\n";
    }
}

Compilation message (stderr)

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:59:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen ("test.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:60:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen ("test.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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