제출 #1168519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168519		thinknoexit	Examination (JOI19_examination)	C++20	100 / 100	1479 ms	154084 KiB

examination

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 100100;
struct A {
    int s, t;
    bool operator < (const A& o) const {
        return s + t < o.s + o.t;
    }
} a[N];
struct Q {
    int x, y, z, i;
    bool operator < (const Q& o) const {
        if (x != o.x) return x > o.x;
        return i < o.i;
    }
};
int sum[N];
vector<Q> v;
int ans[N], n;
ordered_set<pair<int, int>> seg_tree[4 * N];
void update(int v, int w, int now = 1, int l = 1, int r = n) {
    seg_tree[now].insert({ w, v });
    if (l == r) return;
    int mid = (l + r) / 2;
    if (v <= mid) update(v, w, 2 * now, l, mid);
    else update(v, w, 2 * now + 1, mid + 1, r);
}
int query(int ql, int qr, int w, int now = 1, int l = 1, int r = n) {
    if (ql <= l && r <= qr) {
        int ans = (int)seg_tree[now].size()
            - seg_tree[now].order_of_key(pair<int, int>(w, 0));
        return ans;
    }
    int mid = (l + r) / 2;
    if (qr <= mid) return query(ql, qr, w, 2 * now, l, mid);
    if (ql > mid) return query(ql, qr, w, 2 * now + 1, mid + 1, r);
    return query(ql, qr, w, 2 * now, l, mid) + query(ql, qr, w, 2 * now + 1, mid + 1, r);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> n >> q;
    for (int i = 1;i <= n;i++) {
        cin >> a[i].s >> a[i].t;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1;i <= n;i++) {
        sum[i] = a[i].s + a[i].t;
    }
    for (int i = 1;i <= n;i++) {
        v.push_back({ a[i].s, i, -1, -1 });
    }
    for (int i = 1;i <= q;i++) {
        int x, y, z;
        cin >> x >> y >> z;
        v.push_back({ x, y, z, i });
    }
    sort(v.begin(), v.end());
    for (auto& x : v) {
        if (x.i == -1) {
            update(x.y, a[x.y].t);
            continue;
        }
        int idx = lower_bound(sum + 1, sum + 1 + n, x.z) - sum;
        if (idx == n + 1) continue;
        ans[x.i] = query(idx, n, x.y);
    }
    for (int i = 1;i <= q;i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}
/*
80 3 -1 -1
70 5 -1 -1
60 60 80 3
45 1 -1 -1
35 4 -1 -1
20 2 -1 -1
20 50 120 1
10 10 100 2
0 100 100 4
*/

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