Submission #640900

#	Time	Username	Problem	Language	Result	Execution time	Memory
640900		onlk97	Examination (JOI19_examination)	C++14	100 / 100	464 ms	13132 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
bool cmp1(pair <int,int> a,pair <int,int> b){
	return a.second>b.second;
}
bool cmp2(pair <pair <int,int>,pair <int,int> > a,pair <pair <int,int>,pair <int,int> > b){
	return a.first.second>b.first.second;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,q;
	cin>>n>>q;
	pair <int,int> a[n];
	for (int i=0; i<n; i++) cin>>a[i].first>>a[i].second;
	pair <pair <int,int>,pair <int,int> > qu[q];
	for (int i=0; i<q; i++) cin>>qu[i].first.first>>qu[i].first.second>>qu[i].second.first;
	for (int i=0; i<q; i++) qu[i].second.second=i;
	int ans[q];
	for (int i=0; i<q; i++) ans[i]=0;
	{
		sort(a,a+n,cmp1);
		sort(qu,qu+q,cmp2);
		int ptr=0;
		tree <int,null_type,greater_equal <int>,rb_tree_tag,tree_order_statistics_node_update> s;
		for (int i=0; i<q; i++){
			if (qu[i].first.first+qu[i].first.second<qu[i].second.first) continue;
			while (ptr<n&&a[ptr].second>=qu[i].first.second){
				s.insert(a[ptr].first);
				ptr++;
			}
			ans[qu[i].second.second]=s.order_of_key(qu[i].first.first-1);
		}
	}
	{
		int ptr=0;
		tree <int,null_type,greater_equal <int>,rb_tree_tag,tree_order_statistics_node_update> s;
		for (int i=0; i<q; i++){
			if (qu[i].first.first+qu[i].first.second>=qu[i].second.first) continue;
			while (ptr<n&&a[ptr].second>=qu[i].first.second){
				s.insert(a[ptr].first+a[ptr].second);
				ptr++;
			}
			ans[qu[i].second.second]+=s.order_of_key(qu[i].second.first-1);
		}
	}
	{
		sort(a,a+n);
		sort(qu,qu+q);
		int ptr=0;
		tree <int,null_type,greater_equal <int>,rb_tree_tag,tree_order_statistics_node_update> s;
		for (int i=0; i<q; i++){
			if (qu[i].first.first+qu[i].first.second>=qu[i].second.first) continue;
			while (ptr<n&&a[ptr].first<qu[i].first.first){
				s.insert(a[ptr].first+a[ptr].second);
				ptr++;
			}
			ans[qu[i].second.second]-=s.order_of_key(qu[i].second.first-1);
		}
	}
	for (int i=0; i<q; i++) cout<<ans[i]<<'\n';
}

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