P1502″ stars

Title Description

In the evening, Ka looked out from the balcony and said, “Wow, lots of stars.” But he didn’t have a window for the other rooms. The naive Ka always wanted to see the brightest stars at night, but the window was fixed in size and the sides had to be parallel to the ground. At that time, the card used superpower (perspective).You know the position and brightness of each star behind the wall, but the little card gets tired after superpowering, so please tell him that there are at most a total number of bright stars that can appear in the window.

> Input Format:

There are multiple sets of data in the topic, first act.\(T\)Indicates that there are T group data.\(T \le 10\)

For each group of data

first line\(3\)Integers\(n\)，\(W\)，\(H\)，\((n \le 10000,1 \le W,H \le 1000000)\) Indicate that there is\(n\) The width of a star is wide.\(W\)，High\(H\)。

Next\(n\)Row, three integers per row.\(x_i\)，\(y_i\) ，\(l_i\) Represents the coordinates of stars.\((x_i，y_i)\)，Luminance\(l_i\)。\((0 \le l_i,x_i,y_i<2^{31})\)

\(T\)An integer representing the maximum value of the brightness of the window and stars in each group of data.

“

The window frame bought by the little card is made of metal, so it is not included in the frame.

---

The meaning of the explanation is equivalent to the\(w–,h–\)Then make closed intervals, not\(-=2\)The reason is that the window can not be on the integer point.

We take the upper left corner of the rectangle as the position of the rectangle, and then for each star, we have an area that satisfies the brightness of the star when the rectangle falls in that area.

That is to say, we take a point in the set of all star regions to get the maximum brightness.

You can maintain this operation by scanning lines, requiring maintenance interval plus and global maximum.

Because it was the first time to write a scan line, it made a mistake for you to learn from.

When sorting multiple scan lines, if\(x\)When the coordinates are equal, the revocation operation is performed first (if each point is first operated and then inquired).

---

Code:

#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;
const int N=2e4+10;
map <int,int > dx,dy;
int px[N],py[N],shine[N],n,m,w,h,nx,ny;
struct node
{
    int x,up,dow,shine;
    bool friend operator <(node n1,node n2)
    {
        return n1.x==n2.x?n1.shine<n2.shine:n1.x<n2.x;
    }
}line[N];
void init()
{
    dx.clear(),dy.clear();
    scanf("%d%d%d",&n,&w,&h);//Number, length and width--w, --h;For (int i=1; i< =n; i++){Scanf ("%d%d%d", px+i, py+i, shine+i);Dx[px[i]]=1, dy[py[i]]=1;Dx[px[i]-w]=1, dy[py[i]-h]=1;}Nx=0, ny=0;For (map< int, int >:: iterator it=dx.begin (); it! =dx.end (); it++It-> second=++nx;For (map< int, int >:: iterator it=dy.begin (); it! =dy.end (); it++It-> second=++ny;M=0;For (int i=1; i< =n; i++){Line[++m]={dx[px[i]]+1, dy[py[i]-h], dy[py[i]], -shine[i]};Line[++m]={dx[px[i]-w], dy[py[i]-h], dy[py[i]], shine[i]};}Sort (line+1, line+1+m);}IntLazy[N< < 2]; mx[N< < 2];#define LS id< < 1#define RS id< < 1|1Void pushdown (int)ID){If (lazy[id]){Lazy[ls]+=lazy[id], lazy[rs]+=lazy[id];Mx[ls]+=lazy[id]Mx[rs]+=lazy[id];Lazy[id]=0;}}Void updata (int ID){Mx[id]=max (mx[ls], mx[rs]);}Void change (int ID, Int l, int r, int L, int, int){If (l==L& & r==R){LAzy[id]+=delta;Mx[id]+=delta;Return;}Pushdown (ID);Int Mid=L+R> &gT; 1;If (r< =Mid) change (LS, l, R, L, Mid, delta);Else if (l> Mid) change (RS, l, R, Mid+1, R, delta));Else change (LS, l, Mid, L, Mid, delta), change (RS, Mid+1, Mid+1, Delta, L).Updata (ID);}Void woRk (){Memset (MX, 0, sizeof (MX));Memset (lazy, 0, sizeof (lazy));Int ans=0;For (int i=1;I< =m; i++){Change (1, line[i].up, line[i].dow, 1, NY, line[i].shine);Ans=max (ANS,Mx[1]);}Printf ("%d\n", ANS);}Int main (){Int t; scanf ("%d\n", & t);While (t--)Init (), work ();Return 0;}

---

2018.8.31