Submission #330894

#	Time	Username	Problem	Language	Result	Execution time	Memory
330894		12tqian	Examination (JOI19_examination)	C++17	100 / 100	2569 ms	373868 KiB

examination

#include<bits/stdc++.h>
using namespace std;
const int SZ = (1 << 18);
// [0, SZ - 1) queries for each axis
template<class T> struct Node {
    T val = 0; 
    Node<T>* c[2];
    Node() { c[0] = c[1] = NULL; }
    void upd(int ind, T v, int L = 0, int R = SZ - 1) { // add v
        if (L == ind && R == ind) { val += v; return; }
        int M = (L + R) / 2;
        if (ind <= M) {
            if (!c[0]) c[0] = new Node();
            c[0]->upd(ind, v, L, M);
        } else {
            if (!c[1]) c[1] = new Node();
            c[1]->upd(ind, v, M + 1, R);
        }
        val = 0; 
        for (int i = 0; i < 2; i++)
            if (c[i]) val += c[i]->val;
    }
    T query(int lo, int hi, int L = 0, int R = SZ - 1) { // query sum of segment
        if (hi < L || R < lo) return 0;
        if (lo <= L && R <= hi) return val;
        int M = (L + R) / 2; 
        T res = 0;
        if (c[0]) res += c[0]->query(lo, hi, L, M);
        if (c[1]) res += c[1]->query(lo, hi, M + 1, R);
        return res;
    }
    void update_2d(int ind, Node* c0, Node* c1, int L = 0, int R = SZ - 1) { // for 2D segtree
        if (L != R) {
            int M = (L + R) / 2;
            if (ind <= M) {
                if (!c[0]) c[0] = new Node();
                c[0]->update_2d(ind, (c0 ? c0->c[0] : NULL), (c1 ? c1->c[0] : NULL), L, M);
            } else {
                if (!c[1]) c[1] = new Node();
                c[1]->update_2d(ind, (c0 ? c0->c[1] : NULL), (c1 ? c1->c[1] : NULL), M + 1, R);
            }
        } 
        val = (c0 ? c0->val : 0) + (c1 ? c1->val : 0);
    }
};
template<class T> struct BITSeg { // 0-indexed implicitly
    std::vector<Node<T>> seg;
    BITSeg() { 
        seg.resize(SZ + 1);
        for (int i = 0; i < SZ; i++)
            seg[i] = Node<T>();
    }
    void upd(int x, int y, int v) { // add v
        x++;
        for (; x < SZ + 1; x += x & -x) 
            seg[x].upd(y, v); 
    }
    T query(int x, int y1, int y2) {
        if (x <= 0) return 0;
        T res = 0; 
        for (; x; x -= x & -x) 
            res += seg[x].query(y1, y2);
        return res; 
    }
    T query(int x1, int x2, int y1, int y2) { // query sum of rectangle
        x1++, x2++;
        return query(x2, y1, y2) - query(x1 - 1, y1, y2); 
    }
};
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q; cin >> n >> q;
    vector<array<int, 2>> v(n);
    set<int> xs, ys;
    for (int i = 0; i < n; i++) {
        cin >> v[i][0] >> v[i][1];
        xs.insert(v[i][0]);
        ys.insert(v[i][1]);
    }
    vector<int> ans(q);
    vector<array<int, 4>> queries(q);
    for (int i = 0; i < q; i++) {
        queries[i][0] = i;
        cin >> queries[i][1] >> queries[i][2] >> queries[i][3];
        xs.insert(queries[i][1]);
        ys.insert(queries[i][2]);
    }
    map<int, int> mx, my;
    int cnt = 0;
    for (int x : xs) 
        mx[x] = cnt, cnt++;
    cnt = 0;
    for (int y : ys)
        my[y] = cnt, cnt++;
    sort(queries.begin(), queries.end(), [](array<int, 4> a, array<int, 4> b) {
        return a[3] < b[3];
    });
    sort(v.begin(), v.end(), [](array<int, 2> a, array<int, 2> b) {
        return a[0] + a[1] < b[0] + b[1];
    });
    BITSeg<int> seg;
    int qv = n;
    for (int i = q - 1; i >= 0; i--) {
        int sum = queries[i][3];
        while (qv > 0 && v[qv - 1][0] + v[qv - 1][1] >= sum) {
            qv--;
            seg.upd(mx[v[qv][0]], my[v[qv][1]], 1);
        }
        ans[queries[i][0]] = seg.query(mx[queries[i][1]], SZ - 1, my[queries[i][2]], SZ - 1);
    }
    for (int i = 0; i < q; i++) 
        cout << ans[i] << '\n';
    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57