제출 #313772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
313772		limabeans	Examination (JOI19_examination)	C++17	100 / 100	2504 ms	157808 KiB

examination

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl


#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>;
//*find_by_order: iterator to kth elem (0-indexed)
//order_of_key: # of items < k (stictly less)


using ll = long long;


const int maxn = 1e5 + 10;

int n, q;
ordered_set<pair<int,int>> t[4*maxn];
vector<pair<int,int>> vx, vy;
vector<array<int, 4>> Q;

int cc = 0;

void upd(int v, int tl, int tr, int i, int sum) {
    t[v].insert({sum,cc++});
    if (tl==tr) {
	return;
    }
    int tm = (tl+tr)/2;
    if (i<=tm) {
	upd(2*v,tl,tm,i,sum);
    } else {
	upd(2*v+1,tm+1,tr,i,sum);
    }
}

int qry(int v, int tl, int tr, int l, int r, int sum) {
    if (l>tr || r<tl) {
	return 0;
    }
    if (l<=tl && tr<=r) {
	return (int)t[v].size() - t[v].order_of_key(make_pair(sum,-1)) ;
    } else {
	int tm = (tl+tr)/2;
	return qry(2*v,tl,tm,l,r,sum) + qry(2*v+1,tm+1,tr,l,r,sum);
    }
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>q;
    for (int i=0; i<n; i++) {
	int x,y;
	cin>>x>>y;
	vx.emplace_back(x,y);
	vy.emplace_back(x,y);
    }

    sort(vx.begin(),vx.end(),[&](pair<int,int> a, pair<int,int> b) {
	    return a<b;
	});

    sort(vy.begin(),vy.end(),[&](pair<int,int> a, pair<int,int> b) {
	    return make_pair(a.second,a.first) < make_pair(b.second,b.first);
	});


    Q.resize(q);
    for (int i=0; i<q; i++) {
	for (int j=0; j<3; j++) {
	    cin>>Q[i][j];
	}
	Q[i][3] = i;
    }

    sort(Q.begin(),Q.end(),[&](array<int,4> a, array<int,4> b) {
	    return a[1] > b[1];
	});



    vector<int> ans(q);
    
    for (auto qu: Q) {
	int x=qu[0];
	int y=qu[1];
	int z=qu[2];
	int i=qu[3];


	while (!vy.empty() && vy.back().second >= y) {
	    pair<int,int> cur = vy.back();
	    vy.pop_back();
	    int idx = lower_bound(vx.begin(),vx.end(),cur) - vx.begin() + 1;
	    upd(1,1,n,idx,cur.first+cur.second);
	}

	int idx = lower_bound(vx.begin(),vx.end(),make_pair(x,-1)) - vx.begin() + 1;
	int res = qry(1,1,n,idx,n,z);
	ans[i] = res;
    }


    for (int x: ans) {
	cout<<x<<"\n";
    }
    
    
    return 0;
}

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