Submission #1209924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209924		TAMREF	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	92 ms	55232 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

int n, q;
vector<string> S;

using sp = string::reverse_iterator;

int c[256];
int fcnt = 1, rcnt = 1;

struct fnode {
    int l[4], mn, mx;
} fnd[2000005];

int fbuild(string &t, int x, bool add=true) {
    int cur = 1;
    for(auto &ch : t) {
        if(add) {
            if(!fnd[cur].mn) fnd[cur].mn = x;
            fnd[cur].mx = x;
        }

        int &nxt = fnd[cur].l[c[int(ch)]];
        if(!nxt) {
            if(!add) return 0;
            nxt = ++fcnt;
        }
        cur = nxt;
    }
    if(add) {
        if(!fnd[cur].mn) fnd[cur].mn = x;
        fnd[cur].mx = x;
    }
    return cur;
}

struct node {
    static int cnt;
    int l[4], v;
} nd[2000005];

int build(sp b, sp e, bool add=true, bool seg=false) {
    int cur = 1;
    for(; b != e; b++) {
        if(seg) ++nd[cur].v;
        int &nxt = nd[cur].l[c[int(*b)]];
        if(!nxt) {
            if(!add) return 0;
            nxt = ++rcnt;
        }
        cur = nxt;
    }
    if(seg) ++nd[cur].v;
    return cur;
}

int ans[2000005];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    c['A'] = 0; c['C'] = 1; c['G'] = 2; c['U'] = 3;

    cin >> n >> q;
    for(int i = 0; i < n; i++) {
        string t;
        cin >> t;
        S.push_back(t);
    }
    sort(S.begin(), S.end());

    // insert, plus, minus
    // time, type, index (type: -1 : minus, 0 : update, 1 : plus)
    vector<tuple<int, int, int>> que;
    for(int i = 0; i < n; i++) {
        fbuild(S[i], i+1);
        int id = build(S[i].rbegin(), S[i].rend());
        que.emplace_back(i, 0, id);
    }

    for(int i = 0; i < q; i++) {
        string s, t;
        cin >> s >> t;
        int fid = fbuild(s, -1, false);
        int rid = build(t.rbegin(), t.rend(), false);

        if(!fid || !rid) continue;
        int l = fnd[fid].mn, r = fnd[fid].mx;
        --l; --r;

        que.emplace_back(l, ~i, rid);
        que.emplace_back(r, i+1, rid);
    }

    sort(que.begin(), que.end());

    for(auto &[g, ty, id] : que) {
        if(ty > 0) {
            ans[ty-1] += nd[id].v;
        } else if (ty < 0) {
            ans[~ty] -= nd[id].v;
        } else {
            build(S[g].rbegin(), S[g].rend(), false, true);
        }
    }

    for(int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }
}

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