제출 #915607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915607		amirhoseinfar1385	Examination (JOI19_examination)	C++17	100 / 100	459 ms	32104 KiB

examination

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int n,q,res[maxn];
struct stu{
	int a,b,c;
	bool operator <(const stu fake)const{
		if(c==fake.c){
			return a<fake.a;
		}
		return c<fake.c;
	}
};
struct qu{
	int a,b,c,ind;
	bool operator <(const qu fake)const{
		if(c==fake.c){
			return a<fake.a;
		}
		return c<fake.c;
	}
};
vector<stu>alls;
vector<qu>allq;

struct fenwick{
	vector<int>fn;
	int sz;
	void create(int a){
		sz=a+10;
		fn.resize(sz);
	}
	void add(int i,int w){
		i++;
		while(i<sz){
			fn[i]+=w;
			i+=((-i)&i);
		}
	}
	int pors(int i){
		i++;
		int ret=0;
		while(i>0){
			ret+=fn[i];
			i-=((-i)&i);
		}
		return ret;
	}
};

struct fenwicka{
	struct node{
		vector<int>v;
		fenwick f;
	};
	node fen[maxn];
	void ins(int i,int w){
		i++;
		while(i<maxn){
			fen[i].v.push_back(w);
			i+=((-i)&i);
		}
	}
	void build(){
		for(int i=0;i<maxn;i++){
			sort(fen[i].v.begin(),fen[i].v.end());
			fen[i].v.resize(unique(fen[i].v.begin(),fen[i].v.end())-fen[i].v.begin());
			fen[i].f.create(fen[i].v.size());
		}
	}
	void upd(int i,int w){
		i++;
		while(i<maxn){
			int p=lower_bound(fen[i].v.begin(),fen[i].v.end(),w)-fen[i].v.begin();
			fen[i].f.add(p,1);
			i+=((-i)&i);
		}
	}
	int pors(int i,int w){
		i++;
		int ret=0;
		while(i>0){
			int p=lower_bound(fen[i].v.begin(),fen[i].v.end(),w)-fen[i].v.begin();
			ret+=fen[i].f.pors((int)fen[i].v.size()+2)-fen[i].f.pors(p-1);
			i-=((-i)&i);
		}
		return ret;
	}
}fen;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	alls.resize(n);
	allq.resize(q);
	vector<int>allind;
	for(int i=0;i<n;i++){
		cin>>alls[i].a>>alls[i].b;
		alls[i].c=alls[i].a+alls[i].b;
		allind.push_back(alls[i].a);
	}
	sort(allind.begin(),allind.end());
	allind.resize(unique(allind.begin(),allind.end())-allind.begin());
	for(int i=0;i<q;i++){
		cin>>allq[i].a>>allq[i].b>>allq[i].c;
		allq[i].ind=i;
	}
	sort(alls.begin(),alls.end());
	sort(allq.begin(),allq.end());
	for(auto x:alls){
		int p=lower_bound(allind.begin(),allind.end(),x.a)-allind.begin();
		fen.ins(p,x.b);
	}
	fen.build();
	while((int)allq.size()>0){
		while((int)alls.size()>0&&alls.back().c>=allq.back().c){
			int p=lower_bound(allind.begin(),allind.end(),alls.back().a)-allind.begin();
			fen.upd(p,alls.back().b);
			alls.pop_back();
		}
		int p=lower_bound(allind.begin(),allind.end(),allq.back().a)-allind.begin();
		res[allq.back().ind]=fen.pors(maxn-2,allq.back().b)-fen.pors(p-1,allq.back().b);
		allq.pop_back();
	}
	for(int i=0;i<q;i++){
		cout<<res[i]<<"\n";
	}
}

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