Submission #888645

#	Time	Username	Problem	Language	Result	Execution time	Memory
888645		box	Examination (JOI19_examination)	C++17	100 / 100	299 ms	15276 KiB

examination

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;

const int N = 1e5, Q = 1e5;

int n, q;
int x[N], y[N], z[N];
int ans[Q];

vector<int> sor(int *a) {
    vector v(a, a + n);
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
    return v;
}

int ft[N];

void add(int i, int x) {
    while (i < n) {
        ft[i] += x;
        i |= i + 1;
    }
}

int sum(int i) {
    int x = 0;
    while (i >= 0) {
        x += ft[i];
        i &= i + 1, i--;
    }
    return x;
}

vector<ar<int, 4>> events;

void rec(int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        rec(l, m);
        rec(m + 1, r);
        vector<ar<int, 2>> one;
        for (int i = l; i <= m; i++) if (events[i][3] == -1) one.push_back({events[i][1], events[i][2]});
        vector<ar<int, 3>> two;
        for (int i = m + 1; i <= r; i++) if (~events[i][3]) two.push_back({events[i][1], events[i][2], events[i][3]});
        sort(begin(one), end(one));
        sort(begin(two), end(two));
        int p = 0;
        for (auto [b, c, h] : two) {
            while (p < sz(one) && b >= one[p][0]) {
                auto [y, z] = one[p++];
                add(z, 1);
            }
            ans[h] += sum(c);
        }
        while (p > 0) {
            auto [y, z] = one[--p];
            add(z, -1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        z[i] = x[i] + y[i];
    }
    auto xx = sor(x);
    auto yy = sor(y);
    auto zz = sor(z);
    for (int i = 0; i < n; i++) {
        x[i] = lower_bound(begin(xx), end(xx), x[i]) - begin(xx);
        y[i] = lower_bound(begin(yy), end(yy), y[i]) - begin(yy);
        z[i] = lower_bound(begin(zz), end(zz), z[i]) - begin(zz);
        events.push_back({x[i], y[i], z[i], -1});
    }
    for (int h = 0; h < q; h++) {
        int a, b, c;
        cin >> a >> b >> c;
        a = lower_bound(begin(xx), end(xx), a) - begin(xx);
        b = lower_bound(begin(yy), end(yy), b) - begin(yy);
        c = lower_bound(begin(zz), end(zz), c) - begin(zz);
        if (a < sz(xx) && b < sz(yy) && c < sz(zz)) events.push_back({a, b, c, h});
    }
    for (auto &[x, y, z, t] : events) {
        x = sz(xx) - x - 1;
        y = sz(yy) - y - 1;
        z = sz(zz) - z - 1;
    }
    sort(begin(events), end(events));
    rec(0, sz(events) - 1);
    for (int h = 0; h < q; h++) cout << ans[h] << "\n";
}

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