WA了#4和#9求大佬帮忙看看
查看原帖
WA了#4和#9求大佬帮忙看看
802878
Shattered_Shade楼主2022/11/25 17:41
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll max_n = 20004;

ll point[2 * max_n];

struct scanline {
	ll leftx;
	ll rightx;
	ll y;
	ll weight;
	void ini(ll a, ll b, ll c, ll d) {
		this->leftx = a;
		this->rightx = b;
		this->y = c;
		this->weight = d;
	}
}line[2*max_n];

struct treenode {
	ll left;
	ll right;
	ll weight;
	ll tag;
	void ini(ll a, ll b, ll c,ll d) {
		this->left = a;
		this->right = b;
		this->weight = c;
		this->tag = d;
	}
}tree[8*max_n];

bool cmp(scanline a, scanline b) {
	return (a.y!=b.y)?a.y < b.y:a.weight>b.weight;
}

void build(ll node,ll leftline,ll rightline) {
	ll leftnode = node * 2, rightnode = node * 2 + 1;
	ll midline = (leftline + rightline) >> 1;
	tree[node].ini(leftline, rightline, 0,0);
	if (leftline == rightline) {
		return;
	}
	else {
		build(leftnode, leftline, midline);
		build(rightnode, midline + 1, rightline);
	}
	return;
}

void pushdown(ll node) {
	ll leftnode = node * 2, rightnode = node * 2 + 1;
	if (tree[node].tag != 0) {
		tree[leftnode].weight += tree[node].tag;
		tree[rightnode].weight += tree[node].tag;
		tree[leftnode].tag += tree[node].tag;
		tree[rightnode].tag += tree[node].tag;
		tree[node].tag = 0;
	}
	return;
}

void pushup(ll node) {
	ll leftnode = node * 2, rightnode = node * 2 + 1;
	tree[node].weight = max(tree[leftnode].weight, tree[rightnode].weight);
	return;
}

void change(ll node, ll leftaim, ll rightaim,ll value) {
	ll leftnode = node * 2, rightnode = node * 2 + 1;
	if (point[tree[node].left] >= rightaim || point[tree[node].right + 1] <= leftaim) {
		return;
	}
	else if (point[tree[node].left]>=leftaim && point[tree[node].right + 1]<=rightaim) {
		tree[node].weight += value;
		tree[node].tag += value;
		return;
	}
	pushdown(node);
	change(leftnode, leftaim, rightaim, value);
	change(rightnode, leftaim, rightaim, value);
	pushup(node);
	return;
}

int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t = 0, n = 0, w = 0, h = 0, x = 0, y = 0,val=0,realn=0,nx=0,ans=0;
	cin >> t;
	while (t--) {
		ans = 0;
		cin >> n>>w>>h;
		realn = n * 2;
		for (int i = 1; i <= n; i++) {
			cin >> x >> y >> val;
			line[2*i-1].ini(x, x + w, y, val);
			line[2 * i].ini(x, x + w, y + h, -val);
			point[2 * i - 1] = x;
			point[2 * i] = x + w;
		}
		sort(point + 1, point + realn + 1);
		nx = unique(point + 1, point + realn + 1) - (point + 1);
		sort(line + 1, line + realn + 1, cmp);
		build(1, 1, nx - 1);
		//cout << '\n';
		for (int i = 1; i <= realn; i++) {
			change(1, line[i].leftx, line[i].rightx, line[i].weight);
			ans = max(tree[1].weight, ans);
		}
		cout << ans<<"\n";
	}
	return 0;
}
2022/11/25 17:41
加载中...