제출 #330832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330832		12tqian	Examination (JOI19_examination)	C++17	2 / 100	3105 ms	658536 KiB

examination

#include<bits/stdc++.h>
const int SZ = (1 << 30);
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 Node2D {
    Node<T> seg; 
    Node2D* c[2];
    Node2D() { c[0] = c[1] = NULL; }
    void upd(int x, int y, T v, int L = 0, int R = SZ - 1) { // add v
        if (L == x && R == x) { seg.upd(y, v); return; }
        int M = (L + R) / 2;
        if (x <= M) {
            if (!c[0]) c[0] = new Node2D();
            c[0]->upd(x, y, v, L, M);
        } else {
            if (!c[1]) c[1] = new Node2D();
            c[1]->upd(x, y, v, M + 1, R);
        }
        seg.upd(y, v); // only for addition
        // seg.update_2d(y, (c[0] ? & c[0]->seg : NULL), (c[1] ? & c[1]->seg : NULL));
    }
    T query(int x1, int x2, int y1, int y2, int L = 0, int R = SZ - 1) { // query sum of rectangle
        if (x1 <= L && R <= x2) return seg.query(y1, y2);
        if (x2 < L || R < x1) return 0;
        int M = (L + R) / 2; 
        T res = 0;
        if (c[0]) res += c[0]->query(x1, x2, y1, y2, L, M);
        if (c[1]) res += c[1]->query(x1, x2, y1, y2, M + 1, R);
        return res;
    }
};
int main() {
    using namespace std;
    typedef long long ll;
    int n, q; cin >> n >> q;
    vector<array<int, 2>> v(n);
    for (int i = 0; i < n; i++) 
        cin >> v[i][0] >> 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];
    }
    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];
    });
    Node2D<ll> 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(v[qv][0], v[qv][1], 1);
        }
        ans[queries[i][0]] = seg.query(queries[i][1], SZ - 1, queries[i][2], SZ - 1);
    }
    for (int i = 0; i < q; i++) 
        cout << ans[i] << '\n';
    return 0;
}

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