Submission #1279946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279946		tranbahien0	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	226 ms	282860 KiB

selling_rna

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define INF 0x3f3f3f3f
#define file(name) if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define el cout << '\n'
#define maxn int(1e6 + 5)

using namespace std;

typedef pair<int, int> pii;

int n, q, pos[maxn];

string pre[maxn], suf[maxn];

int change(char c) {
    if(c == 'A') return 1;
    if(c == 'U') return 2;
    if(c == 'G') return 3;
    if(c == 'C') return 4;
    return 0;
}

struct PrefixTree {
    struct Node {
        Node* child[5];
        int mx, mn;

        Node() {
            memset(child, 0, sizeof child);
            mx = -INF, mn = INF;
        }
    };
    Node* root = new Node();

    void build(string &s, int id) {
        Node* u = root;
        FOR(i, 0, s.size() - 1) {
            int k = change(s[i]);
            if(u -> child[k] == 0) u -> child[k] = new Node();
            u = u -> child[k];
            u -> mn = min(u -> mn, id);
            u -> mx = max(u -> mx, id);
        }
    }

    pii get(string &s) {
        Node* u = root;
        FOR(i, 0, s.size() - 1) {
            int k = change(s[i]);
            if(u -> child[k] == 0) return {-1, -1};
            u = u -> child[k];
        }
        return {u -> mn, u -> mx};
    }
} prefix;

struct SuffixTree {
    struct Node {
        Node* child[5];
        vector<int> id;

        Node() {
            memset(child, 0, sizeof child);
            id.clear();
        }
    };

    Node* root = new Node();

    void build(string &s, int id) {
        Node* u = root;
        FOR(i, 0, s.size() - 1) {
            int k = change(s[i]);
            if(u -> child[k] == 0) u -> child[k] = new Node();
            u = u -> child[k];
            u -> id.push_back(id);
        }
    }

    int get(string &s, int l, int r) {
        if(l == -1 || r == -1) return 0;
        Node* u = root;
        FOR(i, 0, s.size() - 1) {
            int k = change(s[i]);
            if(u -> child[k] == 0) return 0;
            u = u -> child[k];
        }
        return upper_bound(u -> id.begin(), u -> id.end(), r) - lower_bound(u -> id.begin(), u -> id.end(), l);
    }
} suffix;

bool cmp(int x, int y) {
    return pre[x] < pre[y];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    FOR(i, 1, n) {
        cin >> pre[i];
        suf[i] = pre[i];
        reverse(suf[i].begin(), suf[i].end());
        pos[i] = i;
    }
    sort(pos + 1, pos + n + 1, cmp);
    FOR(i, 1, n) {
        prefix.build(pre[pos[i]], i);
        suffix.build(suf[pos[i]], i);
    }
    while(q--) {
        string P, Q;
        cin >> P >> Q;
        reverse(Q.begin(), Q.end());
        cout << suffix.get(Q, prefix.get(P).first, prefix.get(P).second), el;
    }
    return 0;
}

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