Submission #1261390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261390		icebear	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	175 ms	193640 KiB

selling_rna

// ~~ icebear love attttt ~~
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "RNA"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 2e5 + 5;
int numString, numQuery;
string str[N];

int id(char chr) {
    if (chr == 'A') return 0;
    if (chr == 'G') return 1;
    if (chr == 'U') return 2;
    return 3;
}

class Trie {
private:
    struct Node {
        Node *child[4];
        int minIndex, maxIndex;
        Node() {
            REP(i, 4) child[i] = NULL;
            minIndex = inf;
            maxIndex = -inf;
        }
    };

    Node *root;
public:
    Trie() {
        root = new Node();
    }

    void add(string s, int index) {
        Node *p = root;
        for(char chr : s) {
            int pos = id(chr);
            if (p -> child[pos] == NULL) p -> child[pos] = new Node();
            p = p -> child[pos];
            minimize(p -> minIndex, index);
            maximize(p -> maxIndex, index);
        }
    }

    ii query(string s) {
        Node *p = root;
        for(char chr : s) {
            int pos = id(chr);
            if (p -> child[pos] == NULL) return mp(-1, -1);
            p = p -> child[pos];
        }
        return mp(p -> minIndex, p -> maxIndex);
    }
} trie;

class Trie_reverse {
private:
    struct Node {
        Node *child[4];
        vector<int> indexs;
        Node() {
            REP(i, 4) child[i] = NULL;
            indexs.clear();
        }
    };

    Node *root;
public:
    Trie_reverse() {
        root = new Node();
    }

    void add(string s, int index) {
        Node *p = root;
        for(char chr : s) {
            int pos = id(chr);
            if (p -> child[pos] == NULL) p -> child[pos] = new Node();
            p = p -> child[pos];
            p -> indexs.pb(index);
        }
    }

    int query(string s, ii range) {
        Node *p = root;
        for(char chr : s) {
            int pos = id(chr);
            if (p -> child[pos] == NULL) p -> child[pos] = new Node();
            p = p -> child[pos];
        }
        if ((p -> indexs).empty()) return 0;
        int L = lower_bound(all((p -> indexs)), range.first) - (p -> indexs).begin();
        int R = upper_bound(all((p -> indexs)), range.second) - (p -> indexs).begin();
        return R - L;
    }
} trie_rev;

void init(void) {
    cin >> numString >> numQuery;
    FOR(i, 1, numString) cin >> str[i];
    sort(str + 1, str + numString + 1);
    FOR(i, 1, numString) {
        trie.add(str[i], i);
        reverse(all(str[i]));
        trie_rev.add(str[i], i);
    }
}

void process(void) {
    string prefix, suffix;
    while(numQuery--) {
        cin >> prefix >> suffix;
        reverse(all(suffix));
        ii range = trie.query(prefix);
        cout << (range.fi != -1 ? trie_rev.query(suffix, range) : 0) << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//    cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}

Compilation message (stderr)

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

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