马蜂良好玄关求调(孩子调了3h了)
查看原帖
马蜂良好玄关求调(孩子调了3h了)
1025891
XiaoYiii楼主2024/3/2 23:31
#include<bits/stdc++.h>
#define ll long long
#define ls (x << 1)
#define rs (x << 1) | 1
using namespace std;
//快读快写板子
using yyy = int;
inline char gc()
{
    static char BB[1000000], * S = BB, * T = BB;
    return (S == T) && (T = (S = BB) + fread(BB, 1, 1000000, stdin), S == T) ? EOF : *S++;
}
inline yyy qread()
{
    yyy x = 0, f = 1;
    char ch = gc();
    while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = gc(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = gc(); }
    return x * f;
}
inline void qp(ll x)
{
    if (x > 9) qp(x / 10);
    putchar(x % 10 + '0');
    return;
}
inline void qprint(ll x, int y) {
    if (x == 0) { putchar('0');}
    if (x < 0) { putchar('-'); x = abs(x); }
    if(x > 0) qp(x);
    switch (y) {
    case 1: {
        putchar(' ');
        break;
    }
    case 2: {
        putchar('\n');
        break;
    }
    default: {
        break;
    }
    }
    return;
}
ll Max(ll a, ll b) {return (a > b) ? a : b;} 

const int N = 1e4 + 5;
int xcnt, ycnt, ecnt, n, h, w;
ll xbin[2 * N], ybin[2 * N];
ll maxx[16 * N], tag[16 * N], ans;

void update(int x){
    maxx[x] = Max(maxx[ls], maxx[rs]);
}
void down(int x){
    if(tag[x] != 0){
        tag[ls] += tag[x];
        tag[rs] += tag[x];
        maxx[ls] += tag[x];
        maxx[rs] += tag[x];
        tag[x] = 0;
    }
}
void build(int l, int r, int x){
    if(l == r){
        maxx[x] = tag[x] = 0;
        return;
    } 
    int mid = (l + r) >> 1;
    build(l, mid, ls);
    build(mid + 1, r, rs);
    update(x);
}
void add(int A, int B, ll v, int l, int r, int x){
    down(x);
    if(A <= l && B >= r){
        tag[x] += v;
        maxx[x] += v;
        return;
    }

    int mid = (l + r) >> 1;
    if(A <= mid) add(A, B, v, l, mid, ls);
    if(B >= mid + 1) add(A, B, v, mid + 1, r, rs);
    update(x);
}
ll query(int A, int B, int l, int r, int x){
    down(x);
    ll ret = 0;
    if(A <= l && B >= r) return maxx[x];

    int mid = (l + r) >> 1;
    if(A <= mid) ret = Max(query(A, B, l, mid, ls), ret);
    if(B >= mid + 1) ret = Max(query(A, B, mid + 1, r, rs), ret);
    update(x);
    return ret;
}

struct node{
    int l, r;
    ll hh, v;
    bool operator <(const node& B) const{
        return (hh != B.hh) ? hh < B.hh : v < B.v;
    }
}Eve[2 * N];
node Make(int l, int r, ll hh, ll v){
    node tmp;
    tmp.l = l;
    tmp.r = r;
    tmp.v = v;
    tmp.hh = hh;
    return tmp;
}
struct Tt{
    ll x, y, l;
};
Tt Make_(ll x, ll y, ll l){
    Tt tmp;
    tmp.x = x;
    tmp.y = y;
    tmp.l = l;
    return tmp;
}
vector <Tt> star;
void rd(){
    star.clear();
    ecnt = xcnt = ycnt = 0;
    ans = 0;
    scanf("%d%d%d", &n, &w, &h);
    ll x, y, l;
    for(int i = 1; i <= n; i++){
        scanf("%lld%lld%lld", &x, &y, &l);
        xbin[++xcnt] = x;
        xbin[++xcnt] = x + w * 1ll - 1ll;
        star.push_back(Make_(x, y, l));
    }
}
void prep(){
    sort(xbin + 1, xbin + xcnt + 1);
    xcnt = unique(xbin + 1, xbin + xcnt + 1) - xbin - 1;
    //for(int i = 1; i <= xcnt; i++) qprint(xbin[i], 1);
    //putchar('\n');
    for(int i = 0; i < star.size(); i++){
        int posx = lower_bound(xbin + 1, xbin + xcnt + 1, star[i].x) - xbin;
        int posxx = lower_bound(xbin + 1, xbin + xcnt + 1, star[i].x + w * 1ll - 1ll) - xbin;

        Eve[++ecnt] = Make(posx, posxx, star[i].y, star[i].l);
        Eve[++ecnt] = Make(posx, posxx, star[i].y + h * 1ll - 1 * 1ll, (-1) * star[i].l);
    }
    sort(Eve + 1, Eve + ecnt + 1);
    build(1, xcnt, 1);
}

void solve(){
    ll ret = 0;
    for(int e = 1; e <= ecnt; e++){
        add(Eve[e].l, Eve[e].r, Eve[e].v, 1, xcnt, 1);
        ret = query(1, xcnt, 1, xcnt, 1);
        ans = Max(ans, ret);
    }
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        rd();
        prep();
        solve();
        qprint(ans, 2);
    }
    return 0;
}
2024/3/2 23:31
加载中...