제출 #443952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443952		Jasiekstrz	Examination (JOI19_examination)	C++17	100 / 100	413 ms	29564 KiB

examination

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
const int N=1e5;
struct Que
{
	int x,y,z;
	int id;
};
tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> os,osa,osb;
vector<Que> type1,type2;
int ans[N+10];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;
		type1.push_back({x,y,x+y,0});
		type2.push_back({x,y,x+y,0});
	}
	for(int i=1;i<=q;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		if(x+y>=z)
			type1.push_back({x,y,z,i});
		else
			type2.push_back({x,y,z,i});
	}
	int it=0;
	
	// TYPE 1 (z not important)
	sort(type1.begin(),type1.end(),[](Que &a,Que &b){return (a.x>b.x || (a.x==b.x && a.id<b.id));});
	for(auto v:type1)
	{
		if(v.id==0)
			os.insert({v.y,++it});
		else
		{
			ans[v.id]=os.size()-os.order_of_key({v.y,0});
			//cerr<<"type1 "<<v.id<<" "<<os.size()<<" "<<os.order_of_key({v.y,0})<<"\n";
		}
	}

	// TYPE 2 (z important)
	sort(type2.begin(),type2.end(),[](Que &a,Que &b){return (a.z>b.z || (a.z==b.z && a.id<b.id));});
	for(auto v:type2)
	{
		if(v.id==0)
		{
			osa.insert({v.x,++it});
			osb.insert({v.y,++it});
		}
		else
		{
			ans[v.id]=osa.size()-osa.order_of_key({v.x,0})-osb.order_of_key({v.y,0});
			//cerr<<"type2 "<<v.id<<" "<<os.size()<<" "<<os.order_of_key({v.y,0})<<"\n";
		}
	}

	for(int i=1;i<=q;i++)
		cout<<ans[i]<<"\n";
	return 0;
}

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