제출 #947751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947751		Pring	Examination (JOI19_examination)	C++17	100 / 100	392 ms	70424 KiB

examination

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
typedef array<int, 3> p3i;

const int MXN = 100005, LGC = 32, MXC = 2000000005;
int n, m;
pii a[MXN];
p3i c[MXN];
pii rl[MXN], rr[MXN], rd[MXN];
int ans[MXN];

struct P {
    int t, type, id;
    P() {}
    P(int _t, int _ty, int _id) : t(_t), type(_ty), id(_id) {}
    bool operator<(P o) {
        if (t != o.t) return t < o.t;
        if (type != o.type) return type < o.type;
        return id < o.id;
    }
};

vector<P> swp1, swp2;

struct SMG {
#define mid ((l + r) >> 1)
    int val[MXN * LGC], L[MXN * LGC], R[MXN * LGC];
    int nc;

    int new_node() {
        val[nc] = 0;
        L[nc] = 0;
        R[nc] = 0;
        return nc++;
    }

    void init() {
        nc = 1;
        new_node();
    }

    int modify(int id, int l, int r, int p, int v) {
        if (id == 0) id = new_node();
        if (l + 1 == r) {
            val[id] += v;
            return id;
        }
        if (p < mid) L[id] = modify(L[id], l, mid, p, v);
        else R[id] = modify(R[id], mid, r, p, v);
        val[id] = val[L[id]] + val[R[id]];
        return id;
    }

    int query(int id, int l, int r, int _l, int _r) {
        if (_r <= l || r <= _l) return 0;
        if (_l <= l && r <= _r) return val[id];
        return query(L[id], l, mid, _l, _r) + query(R[id], mid, r, _l, _r);
    }

#undef mid
} smg;

void PUT(int id) {
    auto [x, y, z] = c[id];
    rl[id] = mp(0, x);
    swp1.push_back(P(MXC, 1, id));
    if (x + y >= z) {
        rr[id] = mp(x, MXC);
        swp1.push_back(P(y - 1, 2, id));
    } else {
        rr[id] = mp(z - y, MXC);
        swp1.push_back(P(y - 1, 2, id));
        rd[id] = mp(x, z - y);
        swp2.push_back(P(z - 1, 3, id));
    }
}

void RUN(vector<P> &swp) {
    sort(swp.begin(), swp.end());
    smg.init();
    for (auto [t, type, id] : swp) {
        if (type == 0) {
            smg.modify(1, 0, MXC, a[id].fs, 1);
        } else if (type == 1) {
            ans[id] += smg.query(1, 0, MXC, rl[id].fs, rl[id].sc);
        } else if (type == 2) {
            ans[id] += smg.query(1, 0, MXC, rr[id].fs, rr[id].sc);
        } else {
            ans[id] += smg.query(1, 0, MXC, rd[id].fs, rd[id].sc);
        }
    }
}

void SWP1() {
    FOR(i, 0, n) swp1.push_back(P(a[i].sc, 0, i));
    RUN(swp1);
}

void SWP2() {
    FOR(i, 0, n) swp2.push_back(P(a[i].fs + a[i].sc, 0, i));
    RUN(swp2);
}

void miku() {
    cin >> n >> m;
    FOR(i, 0, n) cin >> a[i].fs >> a[i].sc;
    FOR(i, 0, m) cin >> c[i][0] >> c[i][1] >> c[i][2];
    FOR(i, 0, m) PUT(i);
    SWP1();
    SWP2();
    FOR(i, 0, m) cout << n - ans[i] << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

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