Submission #157197

#	Time	Username	Problem	Language	Result	Execution time	Memory
157197		atoiz	Examination (JOI19_examination)	C++14	100 / 100	280 ms	5608 KiB

examination

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <cstring>
#include <tuple>

using namespace std;

const int MAXN = 100007, MAXC = 2e9 + 7;
vector<int> val_x, val_y;
pair<int, int> pnts[MAXN];
int N, Q, X[MAXN], Y[MAXN], Z[MAXN], ans[MAXN];
vector<int> queries;

struct IT2D
{
    int bit[MAXN];
    void init() { memset(bit, 0, sizeof bit); }
    void upd(int i, int x) { for (++i; i < MAXN; i += i & (-i)) bit[i] += x; }
    int get(int i) { int ans = 0; for (++i; i > 0; i -= i & (-i)) ans += bit[i]; return ans; }
} bit_x, bit_y;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> Q;
    for (int i = 0; i < N; ++i) {
        cin >> pnts[i].first >> pnts[i].second;
        val_x.push_back(pnts[i].first);
        val_y.push_back(pnts[i].second);
    }
    sort(val_x.begin(), val_x.end()); val_x.erase(unique(val_x.begin(), val_x.end()), val_x.end());
    sort(val_y.begin(), val_y.end()); val_y.erase(unique(val_y.begin(), val_y.end()), val_y.end());

    for (int i = 0; i < Q; ++i) { cin >> X[i] >> Y[i] >> Z[i]; Z[i] = max(Z[i], X[i] + Y[i]); }
    queries.resize(Q);
    iota(queries.begin(), queries.end(), 0);

    // iterate x
    sort(pnts, pnts + N, [&](pair<int, int> p1, pair<int, int> p2) { return p1.first < p2.first; } );
    sort(queries.begin(), queries.end(), [&](int i, int j) { return X[i] < X[j]; });
    bit_x.init(); bit_y.init();

    for (int i = 0, j = 0; i < N || j < Q;) {
        if (j < Q && (i == N || X[queries[j]] <= pnts[i].first)) {
            ans[queries[j]] += i;
            ++j;
        } else {
            bit_y.upd(lower_bound(val_y.begin(), val_y.end(), pnts[i].second) - val_y.begin(), 1);
            ++i;
        }
    }
    // cerr << "S" << endl;
    for (int id = 0; id < Q; ++id) ans[id] += bit_y.get(lower_bound(val_y.begin(), val_y.end(), Y[id]) - val_y.begin() - 1);


    // iterate x + y), 0);
    sort(pnts, pnts + N, [&](pair<int, int> p1, pair<int, int> p2) { return p1.first + p1.second < p2.first + p2.second; } );
    sort(queries.begin(), queries.end(), [&](int i, int j) { return Z[i] < Z[j]; });
    bit_x.init(); bit_y.init();

    for (int i = 0, j = 0; i < N || j < Q;) {
        if (j < Q && (i == N || Z[queries[j]] <= pnts[i].first + pnts[i].second)) {
            ans[queries[j]] += i;
            ans[queries[j]] -= bit_x.get(lower_bound(val_x.begin(), val_x.end(), X[queries[j]]) - val_x.begin() - 1);
            ans[queries[j]] -= bit_y.get(lower_bound(val_y.begin(), val_y.end(), Y[queries[j]]) - val_y.begin() - 1);
            ++j;
        } else {
            bit_x.upd(lower_bound(val_x.begin(), val_x.end(), pnts[i].first) - val_x.begin(), 1);
            bit_y.upd(lower_bound(val_y.begin(), val_y.end(), pnts[i].second) - val_y.begin(), 1);
            ++i;
        }
    }

    for (int i = 0; i < Q; ++i) {
        cout << N - ans[i] << '\n';
    }
}

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