You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
70 lines
2.1 KiB
70 lines
2.1 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 2e5 + 10;
|
|
//插入点(x,y) 插入竖线 [y,y+h 区间+1
|
|
//删除点(x+w,y) 删除竖线 [y,y+h] 区间-1
|
|
//对纵坐标离散化后建树
|
|
//按x坐标增序插入点 询问某一时刻区间最大值
|
|
struct node {
|
|
int x, y, yy, v; //一条(x,y)到(x,yy)的竖直线 +1 -1
|
|
} b[N];
|
|
bool operator<(node a, node b) {
|
|
if (a.x == b.x) return a.v > b.v; //先插入 后删除
|
|
return a.x < b.x;
|
|
}
|
|
int n, k, x, y;
|
|
int Y[N], cnt;
|
|
int ans;
|
|
int mx[4 * N], cov[4 * N];
|
|
void pushdown(int p, int l, int r) {
|
|
if (cov[p]) {
|
|
mx[p << 1] += cov[p];
|
|
cov[p << 1] += cov[p];
|
|
mx[p << 1 | 1] += cov[p];
|
|
cov[p << 1 | 1] += cov[p];
|
|
cov[p] = 0;
|
|
}
|
|
}
|
|
void update(int p, int l, int r, int ql, int qr, int v) {
|
|
if (ql <= l && r <= qr) {
|
|
mx[p] += v;
|
|
cov[p] += v;
|
|
return;
|
|
}
|
|
pushdown(p, l, r);
|
|
int mid = (l + r) / 2;
|
|
if (ql <= mid) update(p << 1, l, mid, ql, qr, v);
|
|
if (qr > mid) update(p << 1 | 1, mid + 1, r, ql, qr, v);
|
|
mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
|
|
}
|
|
int ask(int p, int l, int r, int ql, int qr) {
|
|
if (ql <= l && r <= qr) return mx[p];
|
|
pushdown(p, l, r);
|
|
int mid = (l + r) / 2, ans = 0;
|
|
if (ql <= mid) ans = max(ans, ask(p << 1, l, mid, ql, qr));
|
|
if (qr > mid) ans = max(ans, ask(p << 1 | 1, mid + 1, r, ql, qr));
|
|
return ans;
|
|
}
|
|
int main() {
|
|
scanf("%d%d", &n, &k);
|
|
for (int i = 1; i <= n; ++i) {
|
|
scanf("%d%d", &x, &y);
|
|
b[2 * i - 1] = node{x, y, y + k, 1};
|
|
b[2 * i] = node{x + k, y, y + k, -1};
|
|
Y[++cnt] = y;
|
|
Y[++cnt] = y + k;
|
|
}
|
|
sort(Y + 1, Y + cnt + 1);
|
|
cnt = unique(Y + 1, Y + cnt + 1) - (Y + 1);
|
|
for (int i = 1; i <= 2 * n; ++i) {
|
|
b[i].y = lower_bound(Y + 1, Y + cnt + 1, b[i].y) - Y;
|
|
b[i].yy = lower_bound(Y + 1, Y + cnt + 1, b[i].yy) - Y;
|
|
}
|
|
sort(b + 1, b + 2 * n + 1);
|
|
for (int i = 1; i <= 2 * n; ++i) {
|
|
update(1, 1, cnt, b[i].y, b[i].yy, b[i].v);
|
|
ans = max(ans, ask(1, 1, cnt, 1, cnt));
|
|
}
|
|
printf("%d\n", ans);
|
|
return 0;
|
|
} |