18分求助|玄关
查看原帖
18分求助|玄关
846041
__xxy_free_ioi__楼主2024/10/31 20:17
#include <bits/stdc++.h>

using namespace std;

#define x first
#define h second

const int N = 5e4 + 10;

int n, d, front = 1, rear, ans;
int vis[N];
pair<int, int> cow[N], q[N];

int main() {
	freopen("P3088_2.in", "r", stdin);
	cin >> n >> d;
	for (int i = 1; i <= n; i++) {
		cin >> cow[i].x >> cow[i].h;
	}
	sort(cow + 1, cow + n + 1);
	for (int i = 1; i <= n; i++) {
		while (front <= rear && q[front].x < cow[i].x - d) front++;
		while (front <= rear && q[rear].h < cow[i].h * 2) rear--;
		if (front <= rear) vis[i]++;
		rear++;
		q[rear] = {cow[i].x, cow[i].h};
	}
	front = 1, rear = 0;
	for (int i = n; i >= 1; i--) {
		while (front <= rear && q[front].x > cow[i].x + d) front++;
		while (front <= rear && q[rear].h < cow[i].h * 2) rear--;
		if (front <= rear) vis[i]++;
		rear++;
		q[rear] = {cow[i].x, cow[i].h};
	}
	for (int i = 1; i <= n; i++) {
		if (vis[i] == 2) ans++;
	}
	cout << ans;
	return 0;
}
2024/10/31 20:17
加载中...