oj.uz

Submission #962620

# Submission time Handle Problem Language Result Execution time Memory
962620 2024-04-14T03:39:49 Z PixelCat Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 127 ms 134776 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 110332 KB Output is correct
2 Correct 19 ms 110264 KB Output is correct
3 Correct 21 ms 110412 KB Output is correct
4 Correct 19 ms 110284 KB Output is correct
5 Correct 18 ms 110420 KB Output is correct
6 Correct 18 ms 110424 KB Output is correct
7 Correct 18 ms 110428 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 118828 KB Output is correct
2 Correct 89 ms 119024 KB Output is correct
3 Correct 92 ms 118988 KB Output is correct
4 Correct 97 ms 119080 KB Output is correct
5 Correct 127 ms 115996 KB Output is correct
6 Correct 121 ms 116064 KB Output is correct
7 Correct 57 ms 119268 KB Output is correct
8 Correct 99 ms 121056 KB Output is correct
9 Correct 91 ms 120944 KB Output is correct
10 Correct 75 ms 118464 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 118728 KB Output is correct
2 Correct 35 ms 114496 KB Output is correct
3 Correct 39 ms 115448 KB Output is correct
4 Correct 34 ms 114896 KB Output is correct
5 Correct 35 ms 114636 KB Output is correct
6 Correct 41 ms 115412 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 110332 KB Output is correct
2 Correct 19 ms 110264 KB Output is correct
3 Correct 21 ms 110412 KB Output is correct
4 Correct 19 ms 110284 KB Output is correct
5 Correct 18 ms 110420 KB Output is correct
6 Correct 18 ms 110424 KB Output is correct
7 Correct 18 ms 110428 KB Output is correct
8 Correct 90 ms 118828 KB Output is correct
9 Correct 89 ms 119024 KB Output is correct
10 Correct 92 ms 118988 KB Output is correct
11 Correct 97 ms 119080 KB Output is correct
12 Correct 127 ms 115996 KB Output is correct
13 Correct 121 ms 116064 KB Output is correct
14 Correct 57 ms 119268 KB Output is correct
15 Correct 99 ms 121056 KB Output is correct
16 Correct 91 ms 120944 KB Output is correct
17 Correct 75 ms 118464 KB Output is correct
18 Correct 40 ms 118728 KB Output is correct
19 Correct 35 ms 114496 KB Output is correct
20 Correct 39 ms 115448 KB Output is correct
21 Correct 34 ms 114896 KB Output is correct
22 Correct 35 ms 114636 KB Output is correct
23 Correct 41 ms 115412 KB Output is correct
24 Correct 89 ms 120260 KB Output is correct
25 Correct 100 ms 121396 KB Output is correct
26 Correct 90 ms 119772 KB Output is correct
27 Correct 91 ms 120216 KB Output is correct
28 Correct 123 ms 134776 KB Output is correct
29 Correct 83 ms 128712 KB Output is correct