제출 #1246749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246749		BuiDucManh123	Examination (JOI19_examination)	C++20	0 / 100	159 ms	17688 KiB

examination

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define taskname ""
#define ld long double
using namespace std;

struct Node {
    ll x, y, z;
    int type;
    int id;
};

vector<Node> ev;
vector<ll> Z;
vector<ll> ans;
vector<int> bit;

void bit_update(int i, int v) {
    for (; i < (int)bit.size(); i += i & -i)
        bit[i] += v;
}

int bit_query(int i) {
    int s = 0;
    for (; i > 0; i -= i & -i)
        s += bit[i];
    return s;
}

void cdq(int l, int r) {
    if (l >= r) return;
    int m = (l + r) >> 1;
    cdq(l, m);
    cdq(m + 1, r);
    static vector<Node> tmp;
    tmp.clear();
    int i = l, j = m + 1;
    while (i <= m && j <= r) {
        if (ev[i].y <= ev[j].y) {
            if (ev[i].type == 0)
                bit_update((int)ev[i].z, 1);
            tmp.pb(ev[i++]);
        } else {
            if (ev[j].type == 1)
                ans[ev[j].id] += bit_query((int)ev[j].z);
            tmp.pb(ev[j++]);
        }
    }
    while (i <= m) {
        if (ev[i].type == 0)
            bit_update((int)ev[i].z, 1);
        tmp.pb(ev[i++]);
    }
    while (j <= r) {
        if (ev[j].type == 1)
            ans[ev[j].id] += bit_query((int)ev[j].z);
        tmp.pb(ev[j++]);
    }
    for (int k = l; k <= m; ++k)
        if (ev[k].type == 0)
            bit_update((int)ev[k].z, -1);
    for (int k = l; k <= r; ++k)
        ev[k] = tmp[k - l];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    cin >> N >> Q;
    ev.reserve(N + Q);
    Z.reserve(N + Q);
    ans.assign(Q, 0);

    for (int i = 0; i < N; ++i) {
        ll S, T;
        cin >> S >> T;
        ev.pb({-S, -T, -(S + T), 0, -1});
        Z.pb(-(S + T));
    }
    for (int i = 0; i < Q; ++i) {
        ll X, Y, Zq;
        cin >> X >> Y >> Zq;
        ev.pb({-X, -Y, -Zq, 1, i});
        Z.pb(-Zq);
    }

    sort(Z.begin(), Z.end());
    Z.erase(unique(Z.begin(), Z.end()), Z.end());
    for (auto &e : ev)
        e.z = lower_bound(Z.begin(), Z.end(), e.z) - Z.begin() + 1;

    bit.assign(Z.size() + 5, 0);

    sort(ev.begin(), ev.end(), [](auto &a, auto &b){
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });
    cdq(0, (int)ev.size() - 1);

    for (int i = 0; i < Q; ++i)
        cout << ans[i] << "\n";
    return 0;
}

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