Submission #213198

#	Time	Username	Problem	Language	Result	Execution time	Memory
213198		someone_aa	Examination (JOI19_examination)	C++17	100 / 100	2177 ms	165880 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
using namespace __gnu_pbds;
const int maxn = 100100;

typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> order_set;

struct query{
public:
	int amin, bmin;
	int smin;
}professor[maxn];

struct score {
public:
	int testa, testb;
	int testsum;
}students[maxn];

bool compare_students(score a, score b) {
	return a.testsum > b.testsum;
}

vector<int>qs[maxn];
int result[maxn];
int n, q, sz;

order_set segment_tree[4*maxn];
set<int>st;
map<int,int>cind;
int originalval[maxn];

void update(int aval, int bval, int li=0, int ri=sz-1, int index=1) {
	segment_tree[index].insert(mp(bval, segment_tree[index].size()));
	if(li != ri) {
		int mid = (li + ri) / 2;

		if(aval <= originalval[mid]) update(aval, bval, li, mid, 2*index);
		else update(aval, bval, mid+1, ri, 2*index+1);
	}
}

int query(int qa, int qb, int li=0, int ri=sz-1, int index=1) {
	if(originalval[ri] < qa) return 0;
	else if(originalval[li] >= qa) {
		int tmp = segment_tree[index].order_of_key(mp(qb, -1));
		return (segment_tree[index].size() - tmp);
	}
	else {
		int mid = (li + ri) / 2;
		return query(qa, qb, li, mid, 2*index) + query(qa, qb, mid+1, ri, 2*index+1);
	}
}

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

	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		cin>>students[i].testa>>students[i].testb;
		st.insert(students[i].testa);
		students[i].testsum = students[i].testa + students[i].testb;
	}
	sort(students+1, students+n+1, compare_students);

	int br = 0;
	for(int i:st) {
		originalval[br] = i;
		br++;
	}
	sz = br;

	for(int i=1;i<=q;i++) {
		cin>>professor[i].amin>>professor[i].bmin>>professor[i].smin;

		if(professor[i].smin > students[1].testsum) {
			result[i] = 0;
			continue;
		}

		int index = 1;
		for(int cekor=n/2;cekor>0;cekor/=2) {
			while(index+cekor<=n && students[index+cekor].testsum >= professor[i].smin) index += cekor;
		}
		qs[index].push_back(i);
	}

	for(int i=1;i<=n;i++) {
		update(students[i].testa, students[i].testb);

		for(auto j:qs[i]) {
			result[j] = query(professor[j].amin, professor[j].bmin);
		}
	}

	for(int i=1;i<=q;i++) {
		cout<<result[i]<<"\n";
	}
}

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