**Analysis: The Lazy Cow [gold] by Philip Sun**

Notice that for a given patch of grass, the locus of all the points that can access that patch of grass forms a square whose sides have slopes 1 and -1. We first rotate the coordinate system 45 degrees counter-clockwise to make the squares easier to handle. We also modify the squares so that only points on the interior (not the edge) of the square can reach the the grass; this makes the later code simpler. We can move each side of the square "out" .5 units on the plane. However, to keep all coordinates integral, we instead double the coordinates, increasing the fineness of the grid, and then slide the square's edges out by 1. For example, square ABCD with A (2,2) and C(8,8) would first be doubled into A(4,4) and C(16,16). We slide the square's edges out and get A(3,3) C(17,17). Now the problem becomes looking through a group of axes-aligned squares to find which region has the most combined grass.

We solve this by doing a left-to-right sweep. We create a left-to-right sorted list of vertical segments, vert[], from the grass patch squares. Each segment stores its x value, bottom y value, top y value, and amount of grass; x, bot, top, and g respectively. Since sweeping through the right edge of a square is leaving the square and reducing the amount of grass, g is negative for right segments. To keep track of the amount of grass in each y-interval during the sweep, we create a sort of modified segment tree. The ith leaf node of the tree represents the segment from ys[i] to ys[i+1], where ys[] is a sorted array of all the squares' vertices' y values. Each inner node represents the segment formed by joining its two child segments. We can easily store this as a complete binary tree in an array. The root has index 0 and node i has children at 2*i+1 and 2*i+2. During our sweep, a given node i in our tree will tell us the maximum amount of grass Bessie could reach if she is located just right of the sweep line and if her location's y value is within the interval represented by node i. At the start of the sweep, the segment tree is full of zeroes and our answer is zero. In each iteration of a loop, we process the next vertical segment, segment i. In the tree, we must increment everything in the range vert[i].bot .. vert[i].top by vert[i].g and then update the answer by querying the tree's root. Finishing the sweep will give us our final answer.

Note that the only query we ever make is for the root node, the maximum grass over all possible y. This allows us to use lazy propagation to speed up tree updates--if all of the range represented by node i is to be incremented, we don't pass this update to i's children, since we will never query i's children. We store updates to the range in alone[i] and consider grass from child nodes in total[i], with total[i] = alone[i] + max(total[child1], total[child2]). It is well known that at most two nodes in each level will be changed by such a lazy update. For each change, we need to verify that the changed node's ancestors still store the correct data. This leads to O(log^2 N) time per update, so O(N log^2 N) time overall, which is sufficiently fast for N=100000.

Solution code is as follows:

#include <fstream> #include <cstring> #include <vector> #include <algorithm> #define TMAX 540000 // Segtree can't have more than TMAX elements using namespace std; struct vert { int x, bot, top, g; // x, y of bottom and top, grass amount }; ifstream fin("lazy.in"); ofstream fout("lazy.out"); int n, k; int depth, firstB, numL; // Root depth is zero int total[TMAX], alone[TMAX]; // max grass in interval and lazy helper int startY[TMAX], endY[TMAX]; // the start, end of ith segment bool vComp(vert a, vert b); void inc(int ind, int amt, int a, int b); void fix(int ind); int main() { vector<vert> verts; // All our vertical segments vector<int> ys; // Stores y to construct segtree with fin >> n >> k; for (int i = 0; i < n; i++) { int gi, xi, yi; vert vL, vR; // The left and right vert segments from this square fin >> gi >> xi >> yi; int lxi = xi - k, lyi = yi; // The left point of square int rxi = xi + k, ryi = yi; // The right point of square int llxi_r = 2 * (lxi-lyi) - 1, llyi_r = 2 * (lxi+lyi) - 1; // Lower left after 45 degree spin int urxi_r = 2 * (rxi-ryi) + 1, uryi_r = 2 * (rxi+ryi) + 1; // Upper right after spin vL.g = gi; vR.g = -gi; // Add grass on left, remove on right vL.x = llxi_r; vR.x = urxi_r; vL.bot = llyi_r; vR.bot = llyi_r; vL.top = uryi_r; vR.top = uryi_r; verts.push_back(vL); verts.push_back(vR); ys.push_back(llyi_r); ys.push_back(uryi_r); } sort(verts.begin(), verts.end(), vComp); sort(ys.begin(), ys.end()); ys.resize(unique(ys.begin(), ys.end()) - ys.begin()); // Remove duplicates and resize memset(alone, 0, TMAX * sizeof(int)); // Prepare segtree memset(total, 0, TMAX * sizeof(int)); memset(startY, 0, TMAX * sizeof(int)); memset(endY, 0, TMAX * sizeof(int)); numL = ys.size() - 1; // Number of leaves for (depth = 0; (1 << depth) < numL; depth++) ; firstB = (1 << depth) - 1; // Index of first leaf for (int i = 0; i < numL; i++) { // Get start,end for leaves startY[firstB + i] = ys[i]; endY[firstB + i] = ys[i + 1]; } for (int i = firstB - 1; i >= 0; i--) { // Get start,end for rest of tree startY[i] = min(startY[1 + (i << 1)], startY[2 + (i << 1)]); endY[i] = max(endY[1 + (i << 1)], endY[2 + (i << 1)]); } int ans = 0; for (int i = 0; i < n; i++) { inc(0, verts[i].g, verts[i].bot, verts[i].top); ans = max(ans, total[0]); } fout << ans << "\n"; return 0; } bool vComp(vert a, vert b) { // Sort vertical segs so left is first return (a.x < b.x); } void inc(int ind, int amt, int a, int b) { if (startY[ind] >= b || endY[ind] <= a) return; // a to b is out of range if (startY[ind] >= a && endY[ind] <= b) { // a to b surrounds this seg alone[ind] += amt; total[ind] += amt; fix(ind); // Make sure parents still have correct data return; } inc(1 + (ind << 1), amt, a, b); // a to b partially in seg inc(2 + (ind << 1), amt, a, b); // go to children } void fix(int ind) { // index that was disrupted for (int i = (ind - 1) >> 1; i >= 0; i = (i - 1) >> 1) total[i] = alone[i] + max(total[1 + (i << 1)], total[2 + (i << 1)]); }