求条
查看原帖
求条
1076453
CMH613楼主2024/9/27 22:23

code:

#include<bits/stdc++.h>
using namespace std;
struct node{
	int id,num;
}a[50005];
bool cmp(node x,node y){
	return x.id<y.id;
}
int main(){
	int n,d,ans=0;
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		 cin>>a[i].id>>a[i].num;
	}
	sort(a+1,a+n+1,cmp);
	deque<node> q,w;//q新的,w旧的。
	int e=1;
	while(e<=n&&a[e].id-a[1].id<=d){
		while(!q.empty()&&a[e].num>q.back().num){
			q.pop_back();
		}
		q.push_back(a[e]);
		e++;
	}
	for(int i=1;i<=n;i++){
		while(!q.empty()&&q.front().id<a[i].id){
			node x=q.front();
			q.pop_front();
			while(!w.empty()&&x.num>=w.back().num){
				w.pop_back();
			}
			w.push_back(x);
		}
		while(e<=n&&a[e].id-a[i].id<=d){
			while(!q.empty()&&a[e].num>=q.back().num){
				node x=q.back();
				q.pop_back();
				while(!w.empty()&&x.num>=w.back().num){
					w.pop_back();
				}
				w.push_back(x);
			}
			q.push_back(a[e]);
			e++;
		}
		while(!w.empty()&&a[i].id-w.front().id>d){
			w.pop_front();
		}
		if(!q.empty()&&!w.empty()&&q.front().num>=a[i].num*2&&w.front().num>=a[i].num*2){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}
2024/9/27 22:23
加载中...