Submission #563492

#	Time	Username	Problem	Language	Result	Execution time	Memory
563492		hgmhc	Examination (JOI19_examination)	C++17	100 / 100	252 ms	17632 KiB

examination

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
void o_o(){ cerr << endl; }
template <class H, class...T> void o_o(H h,T...t) { cerr << ' ' << h; o_o(t...); }
#define debug(...) cerr<<'['<<#__VA_ARGS__<<"]:",o_o(__VA_ARGS__)
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define size(x) int((x).size())
#define fi first
#define se second

const int N = 1e5+3, Q = 1e5+3;
int n, q;
ll answer[Q];
struct point { int x, y, z, i; } P[N+Q];
template <const int N>
struct fenwick_tree {
    ll t[N+1] {0,};
    void clear() { fill(t,t+N+1,0); }
    void add(int k, ll x) {
        assert(0 <= k and k < N);
        for (++k; k <= N; k += k&-k) t[k] += x;
    }
    ll pfx(int k) {
        ll s = 0;
        for (++k; k >= 1; k -= k&-k) s += t[k];
        return s;
    }
    ll sum(int l, int r) {
        assert(0 <= l and l <= r and r < N);
        if (l == 0) return pfx(r);
        return pfx(r)-pfx(l-1);
    }
};
fenwick_tree<N+Q> ds;

void dnc(int a = 1, int b = n+q) {
    if (a == b) return;
    int m = (a+b)/2;
    dnc(a,m), dnc(m+1,b);
    // [a,m]: x-내림차순 정렬된 상태, [m+1,b]: x-내림차순 정렬된 상태.
    // [a,m]의 모든 점들은 [m+1,b]보다 z값이 크거나 같음.
    vector<point> tmp;
    int i = a, j = m+1;
    while (i <= m and j <= b) {
        if (P[i].x >= P[j].x) {
            if (P[i].i == 0) ds.add(P[i].y,+1);
            tmp.push_back(P[i++]);
        } else {
            if (P[j].i) answer[P[j].i] += ds.sum(P[j].y,N+Q-1);
            tmp.push_back(P[j++]);
        }
    }
    while (i <= m) {
        if (P[i].i == 0) ds.add(P[i].y,+1);
        tmp.push_back(P[i++]);
    }
    while (j <= b) {
        if (P[j].i) answer[P[j].i] += ds.sum(P[j].y,N+Q-1);
        tmp.push_back(P[j++]);
    }
    rep(k,a,m) if (P[k].i == 0) ds.add(P[k].y,-1);
    rep(k,a,b) P[k] = tmp[k-a];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    vector<int> ys;
    rep(i,1,n) {
        cin >> P[i].x >> P[i].y;
        ys.push_back(P[i].y);
        P[i].z = P[i].x+P[i].y;
        P[i].i = 0;
    }
    rep(j,n+1,n+q) {
        cin >> P[j].x >> P[j].y >> P[j].z;
        ys.push_back(P[j].y);
        P[j].i = j-n;
    }
    sort(all(ys)), ys.erase(unique(all(ys)),end(ys));
    rep(k,1,n+q) P[k].y = lower_bound(all(ys),P[k].y)-begin(ys);
    sort(P+1,P+n+q+1,[](auto &e1, auto &e2) {
        if (e1.z != e2.z) return e1.z > e2.z;
        return e1.i < e2.i;
    });
    dnc();
    rep(j,1,q) cout << answer[j] << '\n';
}

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