#9 WA 调了好久都没调出来,麻烦dalao帮忙看看,谢谢!!!
查看原帖
#9 WA 调了好久都没调出来,麻烦dalao帮忙看看,谢谢!!!
293561
HUNTERman楼主2021/7/24 20:35
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lb;
#define rep(i, f, t) for(int i = f; i <= t; i ++)
#define urep(i, f, t) for(int i = f; i >= t; i --)
#define pb push_back
#define eb emplace_back
#define pq priority_queue
#define umap unordered_map
#define addr(v) v.begin(), v.end()
#define uaddr(v) v.rbegin(), v.rend()
#define mst(arr, val) memset(arr, val, sizeof arr)
#define qstream std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ls(t) (t << 1)
#define rs(t) (t << 1 | 1)
#define lowbit(x) ((x) & (-(x)))
#define ceil_div(a, b) (a + b - 1) / b
//int mid = left + (right - left) / 2;
const ll INF = 1e18 + 7;
const int inf = 0x3f3f3f3f;
const int maxn = 2e4 + 500;
const int Maxn = 2e5 + 5;
const int md = 1e9 + 7;
const int MOD = 100003;
const int Mod = 998244353;
const ll moD = 100000;
const int D = 233;

struct Edge {
    ll x, y1, y2, l = 0;
    bool operator < (Edge b) {
        if(x == b.x) return l > b.l;
        return x < b.x;
    }
} line[maxn];

struct nd {
    ll mx = 0, mark = 0, l, r;
} tree[maxn << 3];

ll T, n, h, w;
ll val[maxn];

inline void push_up(int p) {
    tree[p].mx = max(tree[ls(p)].mx, tree[rs(p)].mx);
}

inline void push_down(int p) {
    if(tree[p].mark) {
        ll tmp = tree[p].mark;
        tree[ls(p)].mark += tmp;
        tree[rs(p)].mark += tmp;
        tree[ls(p)].mx += tmp;
        tree[rs(p)].mx += tmp;
        tree[p].mark = 0;
    }
}

void build(int l, int r, int p = 1) {
    //cout << p << ' ' << l << ' ' << ' ' << r << endl;
    tree[p].mx = tree[p].mark = 0;
    tree[p].l = val[l];
    tree[p].r = val[r];
    if(r <= l + 1) return ;
    int mid = (l + r) >> 1;
    build(l, mid, ls(p));
    build(mid, r, rs(p));
}

void modify(int l, int r, ll z, int p = 1) {
    ll x = tree[p].l, y = tree[p].r;
    if(l <= x && y <= r) {
        tree[p].mark += z;
        tree[p].mx += z;
        return ;
    }
    push_down(p);
    //cout << p << ' ' << l << ' ' << r << ' ' << ls(p) << ' ' << rs(p) << endl;
    if(r > tree[rs(p)].l) modify(l, r, z, rs(p));
    if(l < tree[ls(p)].r) modify(l, r, z, ls(p));
    push_up(p);
}

int main() {
	qstream;
	cin >> T;
    while(T --) {
        cin >> n >> w >> h;
        rep(i, 1, n) {
            ll x, y, l;
            cin >> x >> y >> l;
            line[i] = Edge{x, y, y + h - 1, l};
            line[i + n] = Edge{x + w - 1, y, y + h - 1, -l};
            val[i] = y;
            val[i + n] = y + h - 1;
        }
        sort(line + 1, line + (n << 1) + 1);
        sort(val + 1, val + (n << 1) + 1);
        // rep(i, 1, (n << 1)) cout << val[i] << " ";
        // cout << endl;
        int siz = unique(val + 1, val + (n << 1) + 1) - val - 1;
        build(1, siz);
        ll ans = 0;
        rep(i, 1, (n << 1)) {
            ans = max(ans, tree[1].mx);
            modify(line[i].y1, line[i].y2, line[i].l);
        }
        cout << ans << endl;
    }
	// #ifndef ONLINE_JUDGE
	//     system("pause");
    // #endif
    return 0;
}
2021/7/24 20:35
加载中...