40pts求助
查看原帖
40pts求助
153546
luyiming楼主2021/5/2 16:14
# include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;

# define int long long
int Test;
int n,w,h;

struct Star
{
    int x,y;
    int l;
    Star() {}
    Star(int _x,int _y,int _l) : x(_x),y(_y),l(_l) {}
}a[N];

struct Line
{
    int y,x1,x2,d;
    Line() {}
    Line(int _y,int _x1,int _x2,int _d) : y(_y),x1(_x1),x2(_x2),d(_d) {}
}line[N << 1];

struct node
{
    int Max,lazy;
}T[N << 3];

int b[N << 1];

bool compare(const struct Line &x,const struct Line &y)
{
    // if(x.y == y.y) return x.d > y.d;
    return x.y < y.y;
}

void build(int root,int l,int r)
{
    if(l == r)
    {
        T[root].Max = T[root].lazy = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(root << 1,l,mid);
    build(root << 1 | 1,mid + 1,r);
    return;
}

void pushdown(int root,int l,int r)
{
    if(T[root].lazy == 0) return;
    int mid = (l + r) >> 1,tag = T[root].lazy;
    T[root << 1].lazy += tag;
    T[root << 1 | 1].lazy += tag;
    T[root << 1].Max += tag;
    T[root << 1 | 1].Max += tag;
    T[root].lazy = 0;
    return;
}

void update(int root,int l,int r,int s,int t,int d)
{
    if(l <= s && t <= r)
    {
        T[root].Max += d;
        T[root].lazy += d;
        return;
    }
    pushdown(root,s,t);
    int mid = (s + t) >> 1;
    if(l <= mid) update(root << 1,l,r,s,mid,d);
    if(r > mid) update(root << 1 | 1,l,r,mid + 1,t,d);
    T[root].Max = max(T[root << 1].Max,T[root << 1 | 1].Max);
    return;
}

signed main(void)
{   
    scanf("%lld",&Test);
    while(Test--)
    {
        scanf("%lld%lld%lld",&n,&w,&h);
        for(int i = 1; i <= n; i++)
        {
            scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].l);
            line[i * 2 - 1] = Line(a[i].y,a[i].x,a[i].x + w - 1,a[i].l);
            line[i * 2] = Line(a[i].y + h - 1,a[i].x,a[i].x + w - 1,-a[i].l);
            b[i * 2 - 1] = a[i].x,b[i * 2] = a[i].x + w - 1;
        }
        n <<= 1;
        sort(b + 1, b + n + 1);
        sort(line + 1, line + n + 1, compare);
        int L = unique(b + 1, b + n + 1) - b - 1;
        build(1,1,L);
        int ans = 0;
        for(int i = 1; i <= n; i++)
        {
            line[i].x1 = lower_bound(b + 1, b + L + 1, line[i].x1) - b;
            line[i].x2 = lower_bound(b + 1, b + L + 1, line[i].x2) - b;
            update(1,line[i].x1,line[i].x2,1,L,line[i].d);
            ans = max(ans,T[1].Max);
        }
        printf("%lld\n",ans);
    }
    
    return 0;
}

不知道哪里错了/yiw

2021/5/2 16:14
加载中...