题解

28 条题解

  • 0
    @ 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;
    }

    • @ 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

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

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

    KlogN 空间上MS是扛不住

    不过我旁边的神有办法

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

    我是傻×

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

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

    无穷大不能乱用……

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

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

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

    跟kop那题一样。

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

    没办法……以后再说吧

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

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

    原来扫描线写错:

    while (x[i]

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

    一晚上+WA了10几次=AC

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

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

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

    注意题目描述!!!

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

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

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

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

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

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

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

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

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

    Klogk的?

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

    klogk算法

    数据不大

    呵呵

    23:59:30 AC 此题

    赶上了

    幸福~~

    祝大家都取得好成绩~~

    也祝愿我今年noip一等奖

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

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

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

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

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

    擦。。

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

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

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

    速度真快啊……

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

    浪漫至极~

  • 0
    @ 2009-08-13 12:28:31
    对了流星许愿  
    变成大牛~~  
    貌似没实现啊……  
    还是不会做~
    
  • 0
    @ 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]),然后求最大前缀即可。后面的做法可以应用到下面的这个问题:稀疏矩阵求最大正方形。

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

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

    裸的采矿......

信息

ID
1619
难度
7
分类
数据结构 | 线段树 点击显示
标签
(无)
递交数
351
已通过
61
通过率
17%
上传者