제출 #1160854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160854		Celebi_276	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	185 ms	251908 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define FILE "TEST"
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define ll long long
#define all(v) v.begin(), v.end()

template<class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        } return false; 
    }
template<class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 2E6 + 26;
struct Node {
    int child[4];
    int minId, maxId;
    Node() {
        minId = 2E9 + 29; maxId = 0;
        for (int i = 0; i < 4; i++) child[i] = 0;
    }
} FTrie[N];

struct RNode {
    int child[4];
    vector <int> idList;
    RNode() {
        for (int i = 0; i < 4; i++) child[i] = 0;
    }
} RTrie[N];
short key[91];
int cntNode[2], n, m;
string RNA[N];

void addString (string &s, int id) {
    int u = 0;
    for (int i = 0; i < s.length(); i++) {
        int k = key[s[i]];
        if (!FTrie[u].child[k]) FTrie[u].child[k] = ++cntNode[0];
        u = FTrie[u].child[k];
        minimize(FTrie[u].minId, id);
        maximize(FTrie[u].maxId, id);
    }
}

pair <int, int> getRange (string &pr) {
    int u = 0;
    for (int i = 0; i < pr.length(); i++) {
        int k = key[pr[i]];
        if (!FTrie[u].child[k]) return {-1, -1};
        u = FTrie[u].child[k];
    }
    return {FTrie[u].minId, FTrie[u].maxId};
}

void addRevString (string &s, int id) {
    int u = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        int k = key[s[i]];
        if (!RTrie[u].child[k]) RTrie[u].child[k] = ++cntNode[1];
        u = RTrie[u].child[k];
        RTrie[u].idList.push_back(id);
    }
}

int getQuery (string &s, int l, int r) {
    int u = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        int k = key[s[i]];
        if (!RTrie[u].child[k]) return 0;
        u = RTrie[u].child[k];
    }
    return upper_bound(all(RTrie[u].idList), r) - lower_bound(all(RTrie[u].idList), l);
}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    if (fopen(FILE".INP", "r")) {
        freopen(FILE".INP", "r", stdin);
        freopen(FILE".OUT", "w", stdout);
    }

    key['A'] = 0;
    key['C'] = 1;
    key['G'] = 2;
    key['U'] = 3;

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> RNA[i];
    sort(RNA + 1, RNA + 1 + n);

    for (int i = 1; i <= n; i++) {
        addString(RNA[i], i);
        addRevString(RNA[i], i);
    }

    for (int j = 1; j <= m; j++) {
        string P, Q;
        cin >> P >> Q;
        int l, r;
        tie(l, r) = getRange(P);
        cout << getQuery(Q, l, r) << "\n";
    }

    return 0;
}

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

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(FILE".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(FILE".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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