USACO Contest March 2014 - The Lazy Cow

#include <fstream>
#include <iostream>
#include <set>

#define RIGHT 2097152
#define SIZE 4200000

using namespace std;

ifstream fin("lazy.in");
ofstream fout("lazy.out");

struct Event
{
    int type;
    int x, y1, y2, v;
    Event(int p1, int p2, int p3, int p4, int p5) : type(p1), x(p2), y1(p3), y2(p4), v(p5) {};
    friend bool operator < (Event a, Event b)
    {
        if(a.x < b.x)
            return true;
        if(a.x > b.x)
            return false;
        if(a.type < b.type)
            return true;
        if(a.type > b.type)
            return false;

        return true;
    }
};

enum{DEL, ADD};
int N, K;
int Lazy[SIZE], T[SIZE];
multiset<Event> E;

void update(int l, int r, int v, int n, int a, int b)
{
    if(a > r || b < l)
        return;
    if(a >= l && b <= r)
    {
        T[n] += v;
        Lazy[n] += v;
        return;
    }

    if(Lazy[n] != 0)
    {
        if(a != b)
        {
            Lazy[2*n] += Lazy[n];
            Lazy[2*n + 1] += Lazy[n];
            T[2*n] += Lazy[n];
            T[2*n + 1] += Lazy[n];
        }

        Lazy[n] = 0;
    }

    int mid = (a+b) / 2;
    update(l, r, v, 2*n, a, mid);
    update(l, r, v, 2*n + 1, mid + 1, b);

    T[n] = max(T[2*n], T[2*n + 1]);
}

int main()
{
    fin >> N >> K;

    for(int i = 1; i <= N; i++)
    {
        int g;
        int tx, ty;
        int x, y;

        fin >> g >> tx >> ty;

        x = tx + ty;
        y = ty - tx + 1000001;

        E.insert(Event(ADD, x-K, max(y-K, 1), min(y+K, RIGHT), g));
        E.insert(Event(DEL, x+K+1, max(y-K, 1), min(y+K, RIGHT), -g));
    }

    int ans = 0;

    for(set<Event>::iterator it = E.begin(); it != E.end(); it++)
    {
        update(it->y1, it->y2, it->v, 1, 1, RIGHT);
        ans = max(ans, T[1]);
    }

    cout << ans << "\n";
    fout << ans << "\n";
}