fhq-treap求调
查看原帖
fhq-treap求调
285617
黑影洞人楼主2022/8/1 17:18

一直18分

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define N 1919810
#define int long long
using namespace std;
int n,d,ans;
struct node{
	int x,h;
	void in(){scanf("%lld%lld",&x,&h);}
}a[N];
struct fhq{
	int ch[N][2],mx[N],rnd[N],val[N],key[N],tot,root;
	#define lc ch[x][0]
	#define rc ch[x][1]
	int update(int x){mx[x]=max(mx[x],mx[rc]),mx[x]=max(mx[lc],mx[x]);return x;}
	void split(int p,int k,int &x,int &y){
		if(!p)return void(x=y=0);
		if(key[p]<=k)split(ch[x=p][1],k,ch[p][1],y);
		else split(ch[y=p][0],k,x,ch[p][0]);
		update(p);
	}
	int combine(int x,int y){
		if(!x||!y)return x+y;
		if(rnd[x]<rnd[y]){rc=combine(rc,y);return update(x);}
		else{ch[y][0]=combine(x,ch[y][0]);return update(y);}
	}
	int newnode(int k,int v){
		mx[++tot]=val[tot]=v;key[tot]=k,rnd[tot]=rand();
		return tot;
	}
	void insert(int k,int v){
		int x,y;
		split(root,k,x,y);
		root=combine(x,combine(newnode(k,v),y));
	}
	int query(int l,int r){
		int x,y,z;
		split(root,r,x,y);
		split(x,l-1,x,z);
		int mxn=mx[z];
		root=combine(x,combine(z,y));
		return mxn;
	}
}f;
signed main(){
	srand(time(0));
	scanf("%lld%lld",&n,&d); 
	for(int i=1;i<=n;i++)a[i].in();
	for(int i=1;i<=n;i++)f.insert(a[i].x,a[i].h);
	for(int i=1;i<=n;i++)ans+=(f.query(a[i].x-d,a[i].x-1)>=2*a[i].h&&f.query(a[i].x+1,a[i].x+d)>=2*a[i].h);
	printf("%lld",ans);
	return 0;
}



2022/8/1 17:18
加载中...