Submission #894629

#	Time	Username	Problem	Language	Result	Execution time	Memory
894629		IWKR	Examination (JOI19_examination)	C++17	100 / 100	524 ms	67876 KiB

examination

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

#define int long long

pair<int, int> arr[100001];

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first + a.second < b.first + b.second;
}

struct node {
    int s, e, m;
    vector<int> v;
    vector<int> v2;
    node *l, *r;
    node(int S, int E) {
        s = S;
        e = E;
        m = (s + e) / 2;
        if (s != e) {
            l = new node(s, m);
            r = new node(m + 1, e);
        }
    }
    void update(int X, int V, int V2) {
        v.push_back(V);
        v2.push_back(V2);
        if (X == e) {
            sort(v.begin(), v.end());
            sort(v2.begin(), v2.end());
        }
        if (s != e) {
            if (X <= m) {
                l -> update(X, V, V2);
            } else {
                r -> update(X, V, V2);
            }
        }
    }
    int query(int S, int E, int X, int Y) {
        if (s == S && e == E) {
            int a = lower_bound(v.begin(), v.end(), X) - v.begin();
            int b = lower_bound(v2.begin(), v2.end(), Y) - v2.begin();
            return a + b;
        } else {
            if (E <= m) {
                return l -> query(S, E, X, Y);
            } else if (S > m) {
                return r -> query(S, E, X, Y);
            } else {
                return l -> query(S, m, X, Y) + r -> query(m + 1, E, X, Y);
            }
        }
    }
} *root;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, q;
    cin >> n >> q;
    root = new node(0, n - 1);
    for (int i = 0; i < n; i++) {
        cin >> arr[i].first >> arr[i].second;
    }
    sort(arr, arr + n, cmp);
    for (int i = 0; i < n; i++) {
        root -> update(i, arr[i].first, arr[i].second);
    }
    while (q--) {
        int a, b, c;
        cin >> a >> b >> c;
        c = max(c, a + b);
        int low = -1;
        int high = n - 1;
        while (high - low > 1) {
            int mid = (high + low) / 2;
            if (arr[mid].first + arr[mid].second < c) {
                low = mid;
            } else {
                high = mid;
            }
        }
        if (arr[high].first + arr[high].second < c) {
            cout << 0 << '\n';
            continue;
        }
        int ans = n - high;
        cout << ans - root -> query(high, n - 1, a, b) << '\n';
    }
}

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