Submission #1187691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187691		oviyan_gandhi	Examination (JOI19_examination)	C++17	20 / 100	678 ms	150944 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, greater_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define N 100001
pair<int, int> a[N];
oset<int> seg[4*N];

void build(int l, int r, int pos) {
    for (int i = l; i <= r; i++)
        seg[pos].insert(a[i].second);
    if (l == r) return;
    int mid = (l+r)/2;
    build(l, mid, 2*pos);
    build(mid+1, r, 2*pos+1);
}

int query(int qx, int qy, int l, int r, int pos) {
    if (a[r].first < qx)
        return 0;
    if (a[l].first >= qx)
        return seg[pos].order_of_key(qy-1);
    int mid = (l+r)/2;
    return query(qx, qy, l, mid, 2*pos) + query(qx, qy, mid+1, r, 2*pos+1);
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i].first >> a[i].second;
    sort(a+1, a+n+1);
    build(1, n, 1);
    while (q--) {
        int x, y, z; cin >> x >> y >> z;
        cout << query(x, y, 1, n, 1) << '\n';
    }
    return 0;
}

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