27求条!
查看原帖
27求条!
922691
Hisy楼主2024/4/26 21:18
#include<algorithm>
#include<cstdio>
#define int long long
#define max(num1,num2) ((num1)>(num2)?(num1):(num2))
#define min(num1,num2) ((num1)<(num2)?(num1):(num2))
using namespace std;
struct node{
	int point,high;
	node(void){
		point=high=0; 
	};
};
inline bool compare(node compare1,node compare2){
	return compare1.point<compare2.point;
};
inline int scan(void){
	int minus=1;
	int number=0;
	char got=getchar();
	while('9'<got||got<'0'){
		if(got=='-'){
			minus=-1;
		};
		got=getchar();
	};
	while('0'<=got&&got<='9'){
		number=number*10+got-'0';
		got=getchar();
	};
	return number*minus;
};
inline void print(int answer){
	if(answer<0){
		putchar('-');
		answer=-answer;
	};
	if(answer>9){
		print(answer/10);
	};
	putchar(answer%10+'0');
};
signed main(signed argc,char **argv){
	int maxn=scan(),maxm=scan();
	node *chart=new node[maxn+1];
	node *queue=new node[maxn+1];
	bool *ques=new bool[maxn+1]{false};
	bool *flag=new bool[maxn+1]{false};
	for(int iter=1;iter<=maxn;++iter){
		chart[iter].point=scan();
		chart[iter].high=scan();
	};
	sort(chart+1,chart+maxn+1,compare);
	int top1=1,top2=0;
	for(int iter=1;iter<=maxn;++iter){
		while(top1<=top2&&queue[top2].high<chart[iter].high){
			--top2;
		};
		queue[++top2]=chart[iter];
		while(top1<=top2&&queue[top1].point<chart[iter].point-maxm){
			++top1;
		};
		if(queue[top1].high>=chart[iter].high*2){
			ques[iter]=true;
		};
	};
	for(int iter=0;iter<=maxn;++iter){
		queue[iter]=node();
	};
	top1=1,top2=0;
	for(int iter=maxn;iter>=1;--iter){
		while(top1<=top2&&queue[top2].high<chart[iter].high){
			--top2;
		};
		queue[++top2]=chart[iter];
		while(top1<=top2&&queue[top1].high>chart[iter].point+maxm){
			++top1;
		};
		if(queue[top1].high>=chart[iter].high*2){
			flag[iter]=true;
		};
	};
	int answer=0;
	for(int iter=1;iter<=maxn;++iter){
		if(ques[iter]&&flag[iter]){
			++answer;
		};
	};
	print(answer);
	return 0;
};
2024/4/26 21:18
加载中...