제출 #478205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
478205		Karliver	Examination (JOI19_examination)	C++17	100 / 100	220 ms	12824 KiB

examination

    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()

using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int N = 2e5 + 100;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}

struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};
int A[N], B[N], C[N], S[N], T[N];
V<int> GX, GY;
V<PR<int>> sm;
int n, q;
void solve() {

    cin >> n >> q;

    for(int i = 1;i <= n;++i) {
        cin >> S[i] >> T[i];
        GX.push_back(S[i]);
        GY.push_back(T[i]);
    }

    for(int i = 1;i <= q;++i) {
        cin >> A[i] >> B[i] >> C[i];

        ckma(C[i], A[i] + B[i]);

        GX.push_back(A[i]);
        GY.push_back(B[i]);
    }

    sort(all(GX));
    sort(all(GY));

    GX.erase(unique(all(GX)), GX.end());
    GY.erase(unique(all(GY)), GY.end());
    
    FenwickTree F1(sz(GX) + 2), F2(sz(GY) + 2);

    for(int i = 1;i <= n;++i) sm.push_back({S[i] + T[i], i});

    for(int i = 1;i <= q;++i) sm.push_back({C[i], -i});

    sort(all(sm));
    
    reverse(all(sm));
    int tot = 0;

    V<int> ret(q + 1);
    for(auto &[item, id] : sm) {
        if(id > 0) {
            int p1 = lower_bound(all(GX), S[id]) - GX.begin();
            int p2 = lower_bound(all(GY), T[id]) - GY.begin();

            F1.add(p1, 1);
            F2.add(p2, 1);
            ++tot;
        }
        else {
            id = -id;

            ret[id] = tot;
            int p1 = lower_bound(all(GX), A[id]) - GX.begin();
            int p2 = lower_bound(all(GY), B[id]) - GY.begin();
            ret[id] -= F1.sum(p1 - 1);
            ret[id] -= F2.sum(p2 - 1);
        }
    }

    for(int i = 1;i <= q;++i) cout << ret[i] << ' ';





}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

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