# 28 条题解

• @ 2017-01-26 15:31:18

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -f; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 - '0' + ch, ch = getchar(); }
return x * f;
}

const int K = 10000 + 5;

int n, f, a, b, k, x[K], y[K], w[K], maxv[3000005], addv[3000005];

struct Line {
int x, d, y1, y2;
Line() {}
Line(int x, int d, int y1, int y2): x(x), d(d), y1(y1), y2(y2) {}
bool operator < (const Line& l) const {
if (x == l.x) return d > l.d;
return x < l.x;
}
};

void update(int L, int R, int v, int l, int r, int rt) {
if (L <= l && r <= R) {
maxv[rt] += v;
return;
}
int mid = l + r >> 1;
if (L <= mid) update(L, R, v, l, mid, rt << 1);
if (R > mid) update(L, R, v, mid + 1, r, rt << 1 | 1);
maxv[rt] = max(maxv[rt << 1], maxv[rt << 1 | 1]) + addv[rt];
}

int main() {
scanf("%d%d%d%d%d", &n, &f, &a, &b, &k);
vector<int> ys;
for (int i = 1; i <= k; i++) {
ys.push_back(y[i]);
ys.push_back(y[i] + f);
}
sort(ys.begin(), ys.end());
ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
vector<Line> events;
for (int i = 1; i <= k; i++) {
int y1 = lower_bound(ys.begin(), ys.end(), y[i]) - ys.begin() + 1;
int y2 = lower_bound(ys.begin(), ys.end(), y[i] + f) - ys.begin() + 1;
events.push_back(Line(x[i], w[i], y1, y2));
events.push_back(Line(x[i] + f, -w[i], y1, y2));
}
sort(events.begin(), events.end());
int ans = 0;
for (int i = 0; i < events.size(); i++) {
Line e = events[i];
int d = e.d, y1 = e.y1, y2 = e.y2;
update(y1, y2, d, 1, ys.size(), 1);
ans = max(ans, maxv[1]);
}
printf("%d\n", ans);
return 0;
}

• @ 2017-01-26 15:32:29

扫描线来一发

• @ 2017-01-26 15:33:09

测试数据 #0: Accepted, time = 0 ms, mem = 24412 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 24344 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 24376 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 24480 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 24940 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 24940 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 24940 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 24480 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 24940 KiB, score = 20
Accepted, time = 92 ms, mem = 24940 KiB, score = 100

• @ 2017-01-26 16:03:01

横向区间建立线段树维护，考虑极限情况点在左上角被框住，注意先处理加再处理减

• @ 2010-03-15 19:16:45

KlogN 空间上MS是扛不住

不过我旁边的神有办法

• @ 2010-03-09 21:25:20

我是傻×

明明初始化全为0就好了，非搞个-maxlongint，结果数据爆了

调了一个晚上，交了3回才AC

无穷大不能乱用……

• @ 2009-10-31 13:20:14

无语，原来人在点上，漂亮的一次AC泡汤了

• @ 2009-10-07 10:55:29

跟kop那题一样。

我拿过kop的程序测这题，居然错一个。

没办法……以后再说吧

• @ 2009-09-16 21:15:40

Wa了3次~ 找了1s的题解去对拍~

原来扫描线写错：

while (x[i]

• @ 2009-08-27 21:52:22

一晚上+WA了10几次=AC

这代价也忒大了，最后发现把n和f混用了，n很大，那样数组不爆才怪呢，细节啊...

• @ 2009-08-14 19:24:53

因为k小啊。裸的线段树，没有离散化，KlogN也可以过，可惜不是秒杀。

注意题目描述！！！

比如f=1时，能够覆盖(1,1)和(2,2)两个点。人站的位置是一个点！！！

前3个点WA就是这个原因！

• @ 2009-08-14 17:01:22

1500000也不是很大,klogn+n就行

不过空间太大,怎么省也要内存溢出.只能klogk

此题通过率被我刷下几个百分点,哈哈哈

• @ 2009-08-13 21:10:10

完全不懂....高级数据结构...ORZ....

• @ 2009-08-13 20:48:20

Klogk的？

• @ 2009-08-13 19:37:59

klogk算法

数据不大

呵呵

23：59：30 AC 此题

赶上了

幸福~~

祝大家都取得好成绩~~

也祝愿我今年noip一等奖

• @ 2009-08-13 17:48:47

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

• @ 2009-08-13 15:33:13

不错不错，这题不错，暴搜，我会

• @ 2009-08-13 13:45:05

擦。。

• @ 2009-08-13 13:31:51

流星姐姐为什么要生气呢？？？

• @ 2009-08-13 13:12:39

速度真快啊……

流星雨刚出现就有这道题了……

浪漫至极~

• @ 2009-08-13 12:28:31
``````对了流星许愿
变成大牛~~
貌似没实现啊……
还是不会做~
``````
• @ 2009-08-14 19:46:39

原来K是1W..稀疏图啊

模拟一条长度为s的扫描线，对扫描线内的点，用线段树求出y坐标>=f的最大前缀和即可。

PS：每次对序列某一个数加减，求最大的长度为S的序列和

一种做法是维护s[i]=a[i]~a

另一种做法是，对于任意的a[i]，inc(s[i],a[i]),dec(s,a[i])，然后求最大前缀即可。后面的做法可以应用到下面的这个问题：稀疏矩阵求最大正方形。

注意这道题是给的坐标系上的点，不是格子！！！

• @ 2009-08-13 09:33:09

裸的采矿......

ID
1619

7

(无)

354

64

18%

1