POJ2482

poj2482.cpp

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#include <cstdio>
#define MEM(a,b) memset(a, b, sizeof(a))
using namespace std;

const int N = 20010;

struct line {
    long long x, upper_y, lower_y, v;

    bool operator<(const line b) const {
        if (x == b.x) return v < b.v;
        return x < b.x;
    }
} L[N];

struct node {
    int l, r;
    long long maxv, ins;
} t[N << 2];

int n, w, h;
long long x, y, c;
long long Y[N];
int ycnt;
map<int, int>M;

void init_tree(int root, int l, int r) {
    t[root].l = l;
    t[root].r = r;
    t[root].maxv = t[root].ins = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    init_tree(root * 2, l, mid);
    init_tree(root * 2 + 1, mid + 1, r);
}

void insert_tree(int root, int l, int r, int v) {
    if (t[root].l >= l && t[root].r <= r) {
        t[root].ins += v;
        t[root].maxv += v;
        return;
    }
    int mid = (t[root].l + t[root].r) >> 1;
    if (t[root].ins) {
        t[root * 2].ins += t[root].ins;
        t[root * 2].maxv += t[root].ins;
        t[root * 2 + 1].ins += t[root].ins;
        t[root * 2 + 1].maxv += t[root].ins;
        t[root].ins = 0;
    }
    if (l <= mid)
        insert_tree(root * 2, l, r, v);
    if (r > mid)
        insert_tree(root * 2 + 1, l, r, v);
    t[root].maxv = max(t[root * 2].maxv, t[root * 2 + 1].maxv);
}

int main() {
    while (~scanf("%d%d%d", &n, &w, &h)) {
        ycnt = 0;
        M.clear();
        for (int i = 1; i <= n; i++) {
            scanf("%I64d%I64d%I64d", &x, &y, &c);
            L[2 * i - 1].x = x;
            L[2 * i - 1].upper_y = y + h - 1;
            L[2 * i - 1].lower_y = y;
            L[2 * i - 1].v = c;
            L[2 * i].x = x + w;
            L[2 * i].upper_y = y + h - 1;
            L[2 * i].lower_y = y;
            L[2 * i].v = 0 - c;
            Y[ycnt++] = y;
            Y[ycnt++] = y + h - 1;

        }
        n *= 2;
        sort(L + 1, L + n + 1);
        sort(Y, Y + ycnt);
        int idx = 1;
        M[Y[0]] = idx++;
        for (int i = 1; i < ycnt; i++) {
            if (Y[i] != Y[i - 1]) {
                M[Y[i]] = idx++;
            }
        }
        init_tree(1, 1, idx);
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            insert_tree(1, M[L[i].lower_y], M[L[i].upper_y], L[i].v);
            ans = max(ans, t[1].maxv);
        }
        printf("%I64d\n", ans);

    }
    return 0;
}