Submission #962620

#	Time	Username	Problem	Language	Result	Execution time	Memory
962620		PixelCat	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	127 ms	134776 KiB

selling_rna

#include <bits/stdc++.h>
#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 F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 100'000;
const int MAXND = 2'000'000;

int agcu(const char &ch) {
    if(ch == 'A') return 0;
    if(ch == 'G') return 1;
    if(ch == 'C') return 2;
    if(ch == 'U') return 3;
    assert(false);
    return 8;
}

struct Trie {
    struct Node {
        int nxt[4];
        int cnt;
        int l, r;
        Node() {
            memset(nxt, 0, sizeof(nxt));
            cnt = 0;
            l = r = -1;
        }
    } a[MAXND + 10];
    int _cur_node;
    int _cur_euler;
    int new_node() {
        _cur_node++;
        a[_cur_node] = Node();
        return _cur_node;
    }
    Trie() {
        _cur_node = 0;
        new_node();
        _cur_euler = 1;
    }
    void insert(const string &s) {
        int nd = 1;
        for(auto &i:s) {
            int x = agcu(i);
            if(!a[nd].nxt[x]) a[nd].nxt[x] = new_node();
            nd = a[nd].nxt[x];
        }
        a[nd].cnt++;
    }
    void dfs(int n = 1) {
        a[n].l = _cur_euler;
        _cur_euler += a[n].cnt;
        a[n].r = _cur_euler - 1;
        For(i, 0, 3) if(a[n].nxt[i]) {
            dfs(a[n].nxt[i]);
            a[n].r = a[a[n].nxt[i]].r;
        }
    }
    pii find(const string &s) {
        int cur = 1;
        for(auto &i:s) {
            int x = agcu(i);
            if(!a[cur].nxt[x]) return pii(-1, -1);
            cur = a[cur].nxt[x];
        }
        return pii(a[cur].l, a[cur].r);
    }
} tri, irt;


#define LO(x) ((x) & (-(x)))
struct BIT {
    int n;
    int a[MAXN + 10];
    void init(int _n) {
        n = _n;
        memset(a, 0, sizeof(a));
    }
    void add(int i, int x) {
        while(i <= n) {
            a[i] += x;
            i += LO(i);
        }
    }
    int qry(int i) {
        int res = 0;
        while(i) {
            res += a[i];
            i -= LO(i);
        }
        return res;
    }
    int qry(int l, int r) {
        return qry(r) - qry(l - 1);
    }
} bit;


struct SweepingLine {
    struct Event {
        int qid;  // 0: point, >0: +query, <0: -query
        int t;
        int u, d;
    };
    vector<Event> evt;
    SweepingLine(): evt() {}
    void add_point(int x, int y) {
        evt.push_back({0, y, x, x});
    }
    void add_query(int qid, int xu, int xd, int yl, int yr) {
        if(xu < 0 || yl < 0) return;
        evt.push_back({qid, yr, xu, xd});
        evt.push_back({-qid, yl - 1, xu, xd});
    }
    void eval(int n, int q, vector<int> &ans) {
        sort(all(evt), [&](const Event &e1, const Event &e2) {
            if(e1.t != e2.t) return e1.t < e2.t;
            if((e1.qid != 0) != (e2.qid != 0)) return e1.qid == 0;
            return false;
        });
        reverse(all(evt));
        bit.init(n);
        ans.assign(q + 1, 0);
        while(sz(evt)) {
            Event e = evt.back(); evt.pop_back();
            if(e.qid == 0) {
                bit.add(e.u, 1);
            } else if(e.qid > 0) {
                ans[e.qid] += bit.qry(e.u, e.d);
            } else {
                ans[-e.qid] -= bit.qry(e.u, e.d);
            }
        }
    }
} swp;


int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // =^-w-^=
    int n, q; cin >> n >> q;
    vector<string> s(n), t(n);
    For(i, 0, n - 1) {
        cin >> s[i];
        t[i] = s[i]; reverse(all(t[i]));
        tri.insert(s[i]);
        irt.insert(t[i]);
    }
    tri.dfs();
    irt.dfs();
    For(i, 0, n - 1) {
        swp.add_point(tri.find(s[i]).F, irt.find(t[i]).F);
    }
    For(i, 1, q) {
        string pre, suf; cin >> pre >> suf;
        reverse(all(suf));
        pii rp = tri.find(pre);
        pii rq = irt.find(suf);
        swp.add_query(i, rp.F, rp.S, rq.F, rq.S);
    }
    vector<int> ans;
    swp.eval(n, q, ans);
    For(i, 1, q) cout << ans[i] << "\n";
    return 0;
}

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