제출 #1347620

#제출 시각아이디문제언어결과실행 시간메모리
1347620PieArmyExamination (JOI19_examination)C++20
100 / 100
395 ms51204 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#define sol (node+1)
#define sag (node+((mid-left+1)<<1))

int n,q;
pair<int,int>arr[100023];
int A[100023],B[100023],C[100023];
int per[100023],ans[100023];
map<int,vector<int>>mp;
int m;
vector<int>locs;
int s[200023],sum[200023];
vector<int>tree[200023],vals[200023];

void build(int node=1,int left=0,int right=-1){
	if(right==-1)right=m-1;
	if(left==right){
		vals[node]=mp[locs[left]];
		s[node]=vals[node].size();
		tree[node].resize(s[node]+1,0);
		return;
	}
	build(sol,left,mid);
	build(sag,mid+1,right);
	for(int i=0,j=0;i<s[sol]||j<s[sag];){
		if(i==s[sol]){
			vals[node].pb(vals[sag][j++]);
			continue;
		}
		if(j==s[sag]){
			vals[node].pb(vals[sol][i++]);
			continue;
		}
		if(vals[sol][i]>vals[sag][j]){
			vals[node].pb(vals[sag][j++]);
			continue;
		}
		vals[node].pb(vals[sol][i++]);
		continue;
	}
	vals[node].resize(unique(vals[node].begin(),vals[node].end())-vals[node].begin());
	s[node]=vals[node].size();
	tree[node].resize(s[node]+1,0);
}

int l,r;

void up(int node=1,int left=0,int right=-1){
	if(right==-1)right=m-1;
	int pos=(lower_bound(vals[node].begin(),vals[node].end(),r)-vals[node].begin())+1;
	while(pos<=s[node]){
		tree[node][pos]++;
		pos+=(pos&-pos);
	}
	sum[node]++;
	if(left==right)return;
	if(l>locs[mid])up(sag,mid+1,right);
	else up(sol,left,mid);
}

void update(int a,int b){
	l=a;r=b;
	up();
}

int qu(int node=1,int left=0,int right=-1){
	if(right==-1)right=m-1;
	if(locs[left]>=l){
		int res=sum[node];
		int pos=(lower_bound(vals[node].begin(),vals[node].end(),r)-vals[node].begin());
		while(pos>0){
			res-=tree[node][pos];
			pos-=(pos&-pos);
		}
		return res;
	}
	if(locs[right]<l)return 0;
	return qu(sol,left,mid)+qu(sag,mid+1,right);
}

int query(int a,int b){
	l=a;
	r=b;
	return qu();
}

signed main(){
	ios_base::sync_with_stdio(23^23);cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>arr[i].fr>>arr[i].sc;
	}
	for(int i=1;i<=q;i++){
		cin>>A[i]>>B[i]>>C[i];
	}
	for(int i=1;i<=n;i++){
		mp[arr[i].fr].pb(arr[i].sc);
	}
	for(auto&[x,v]:mp){
		locs.pb(x);
		sort(v.begin(),v.end());
		v.resize(unique(v.begin(),v.end())-v.begin());
	}
	m=locs.size();
	sort(arr+1,arr+n+1,[&](const pair<int,int>&x,const pair<int,int>&y){
		return x.fr+x.sc>y.fr+y.sc;
	});
	iota(per+1,per+q+1,1);
	sort(per+1,per+q+1,[&](const int &x,const int &y){
		return C[x]>C[y];
	});
	build();
	int p=1;
	for(int i=1;i<=q;i++){
		while(p<=n&&arr[p].fr+arr[p].sc>=C[per[i]]){
			update(arr[p].fr,arr[p].sc);
			p++;
		}
		ans[per[i]]=query(A[per[i]],B[per[i]]);
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<endl;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...