MnZn求助扫描线
查看原帖
MnZn求助扫描线
397317
Gym_nastics楼主2021/12/26 20:21

为什么会90分???

求大佬帮忙看一下

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;

int read() {
	char ch=getchar();int x=0,f=0;
	for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');
    for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
	return f?-x:x;
}

void print(int x) {
	if(x<0){putchar('-');x=-x;}
	if(x>9) print(x/10);
	putchar(x%10+48);
}

const int N=1e6+2049;
const int M=2049;

struct Scanline{
    int l,r,h,mark;
    friend bool operator <(Scanline a,Scanline b){
        return a.h<b.h;
    }
}line[N]; 
int n,w,h,X[N];

namespace Seg{
    #define lson pos<<1
    #define rson pos<<1|1
    
    struct node{
        int sum,Max;
    }tree[N<<1];
    
    void push_up(int pos){
        tree[pos].Max=max(tree[lson].Max,tree[rson].Max);
    } 
    
    void push_down(int pos){
        tree[lson].sum+=tree[pos].sum;
        tree[lson].Max+=tree[pos].sum;
        tree[rson].sum+=tree[pos].sum;
        tree[rson].Max+=tree[pos].sum;
        tree[pos].sum=0;
    }
    
    void change(int pos,int l,int r,int L,int R,int k){
        if(l>=L and r<=R){
            tree[pos].sum+=k;
            tree[pos].Max+=k;
            return;
        }
        push_down(pos);int mid=l+r>>1;
        if(L<=mid) change(lson,l,mid,L,R,k);
        if(R>mid) change(rson,mid+1,r,L,R,k);
        push_up(pos);return;
    }
}

signed main() {
   int T=read();
   while(T--){
       n=read();w=read();h=read();
       for(int i=1;i<=n;i++){
           int x=read(),y=read(),l=read();
           X[(i<<1)-1]=x;X[i<<1]=x+w-1;
           line[(i<<1)-1]=(Scanline){x,x+w-1,y,l};
           line[(i<<1) ]=(Scanline){x,x+w-1,y+h-1,-l};
       }n<<=1;
       sort(X+1,X+1+n);sort(line+1,line+1+n);
       int Cnt=unique(X+1,X+1+n)-X-1,Ans=-INF;
       for(int i=1;i<=n;i++){
           line[i].l=lower_bound(X+1,X+1+Cnt,line[i].l)-X;
           line[i].r=lower_bound(X+1,X+1+Cnt,line[i].r)-X;
           Seg::change(1,1,Cnt-1,line[i].l,line[i].r,line[i].mark);
           Ans=max(Ans,Seg::tree[1].Max);
       }
       print(Ans);putchar('\n');
   }
   return 0;
}

2021/12/26 20:21
加载中...