28 条题解
-
0
WeiSama LV 8 @ 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 read() {
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;
addv[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++) {
x[i] = read(), y[i] = read();
w[i] = read() * a + read() * b;
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;
}-
扫描线来一发
-
测试数据 #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 -
横向区间建立线段树维护，考虑极限情况点在左上角被框住，注意先处理加再处理减
-
-
0
chen199277 LV 10 @ 2009-10-07 10:55:29
跟kop那题一样。
我拿过kop的程序测这题，居然错一个。
没办法……以后再说吧 -
0
ufo172849z LV 10 @ 2009-08-14 19:24:53
因为k小啊。裸的线段树，没有离散化，KlogN也可以过，可惜不是秒杀。
注意题目描述！！！
比如f=1时，能够覆盖(1,1)和(2,2)两个点。人站的位置是一个点！！！
前3个点WA就是这个原因！ -
0
hhdllhflower LV 10 @ 2009-08-13 19:37:59
klogk算法
数据不大
呵呵
23：59：30 AC 此题
赶上了
幸福~~
祝大家都取得好成绩~~
也祝愿我今年noip一等奖 -
0
如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html
-
0
JackDavid127 LV 10 @ 2009-08-13 13:12:39
速度真快啊……
流星雨刚出现就有这道题了……浪漫至极~
-
0
hj363059129 LV 9 @ 2009-08-13 12:28:31
对了流星许愿 变成大牛~~ 貌似没实现啊…… 还是不会做~
WeiSama
LV 8
@ 2017-01-26 15:31:18
