萌新刚学oi,求助
查看原帖
萌新刚学oi,求助
536362
baibaieee楼主2023/12/27 17:00

rt,样例过不了,剩下的都能过

#include<bits/stdc++.h>
using namespace std;
const int MAXN=50005;
int n,d,pos[MAXN];
struct cow{
	int tall,pos;
}a[MAXN];
bool cmp(cow a,cow b){
	return a.pos<b.pos;
}
struct Tree{
	int maxn;
}tree[MAXN*4];
void pushup(Tree &a,Tree b,Tree c){
	a.maxn=max(b.maxn,c.maxn);
}
void build(int id=1,int l=1,int r=n){
	if(l==r){
		tree[id].maxn=a[l].tall;
		return;
	}
	int mid=(l+r)>>1;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	pushup(tree[id],tree[id*2],tree[id*2+1]);
}
int query(int ql,int qr,int id=1,int l=1,int r=n){
	if(l>qr||r<ql)return INT_MIN;
	if(l>=ql&&r<=qr)return tree[id].maxn;
	int mid=(l+r)>>1;
	return max(query(ql,qr,id*2,l,mid),query(ql,qr,id*2+1,mid+1,r));
}
int main(){
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		cin>>a[i].pos>>a[i].tall;
		pos[i]=a[i].pos;
	}
	sort(pos+1,pos+n+1);
	sort(a+1,a+n+1,cmp);
	build();
	int ans=0;
	for(int i=1;i<=n;i++){
		int l=lower_bound(pos+1,pos+n+1,max(1,a[i].pos-d))-pos,r=lower_bound(pos+1,pos+n+1,a[i].pos+d)-pos-1;
		if(query(l,i)>=2*a[i].tall&&query(i+1,r)>=2*a[i].tall)ans++;
	}
	cout<<ans;
	return 0;
}
2023/12/27 17:00
加载中...