请求卡常
查看原帖
请求卡常
664063
Lucky_Luo楼主2023/7/18 20:40
#include <bits/stdc++.h>
#define dw(x, y) ((x+y)|(x!=y))
#define max(x, y) (x < y ? y : x)
using namespace std;
typedef long long ll;
const int N = 1e6 + 7, inf = 2e9 + 7;
int i, j, k, l, m, n, ansx=2e9, ansy=2e9, X, Y, w[N<<2];
ll ans=0, res;
int num[N<<1];
struct YZY
{
	int x, y, c;
	#define x(p) d[p].x
	#define y(p) d[p].y
	#define c(p) d[p].c
} d[N];
vector <YZY> g[N<<1];
struct yzy
{
	int u;
	ll s;
	#define s(p) t[p].s
	#define u(p) t[p].u
	bool operator < (const yzy&lq) const {return s < lq.s;}
} t[N<<2];
void build(int x, int y)
{
	int p = dw(x, y);
	if (x == y)
	{
		s(p) = num[x], u(p) = x;
		return;
	}
	int mid = x + y >> 1, lc = dw(x, mid), rc = dw(mid+1, y);
	build(x, mid), build(mid+1, y);
	t[p] = max(t[lc], t[rc]);
}
void upd(int x, int y, int v)
{
	int p = dw(x, y);
	s(p) += v, w[p] += v;
}
void push(int x, int y)
{
	int p = dw(x, y), mid = x + y >> 1;
	if (w[p])
	{
		upd(x, mid, w[p]);
		upd(mid+1, y, w[p]);
		w[p] = 0;
	}
}
void add(int x, int y, int l, int r, int v)
{
	int p = dw(x, y);
	if (l <= x && y <= r) 
	{
		upd(x, y, v);
		return;
	}
	push(x, y);
	int mid = x + y >> 1, lc = dw(x, mid), rc = dw(mid+1, y);
	if (l <= mid) add(x, mid, l, r, v);
	if (r > mid) add(mid+1, y, l, r, v);
	t[p] = max(t[lc], t[rc]);
}
yzy ask(int x, int y, int l, int r)
{
	int p = dw(x, y);
//	if (x == y) return t[p];
	if (l <= x && y <= r) return t[p];
	int mid = x + y >> 1;
	push(x, y);
	yzy res;
	res.s = -inf;
	if (l <= mid) res = max(res, ask(x, mid, l, r));
	if (r > mid) res = max(res, ask(mid+1, y, l, r));
	return res;
}
int main()
{
	scanf("%d", &n);
	for (i=1; i<=n; i++)
	{
		scanf("%d %d %d", &x(i), &y(i), &c(i));
		x(i)++, y(i)++;
		if (x(i) > y(i)) swap(x(i), y(i));
		num[i<<1] = x(i), num[(i<<1)-1] = y(i); 
	}
	sort(num+1, num+n*2+1);
	m = unique(num+1, num+n*2+1) - num - 1;
	for (i=1; i<=n; i++) 
	{
		x(i) = lower_bound(num+1, num+m+1, x(i)) - num;
		y(i) = lower_bound(num+1, num+m+1, y(i)) - num;
		g[y(i)].push_back(d[i]);
	}
	build(1, m);
	for (Y=1; Y<=m; Y++)
	{
		for (i=0; i<g[Y].size(); i++) add(1, m, 1, g[Y][i].x, g[Y][i].c);
		X = ask(1, m, 1, Y).u;
		res = ask(1, m, 1, Y).s - num[Y];
		if (res > ans)
		{
			ans = res;
			ansx = num[X] - 1;
			ansy = num[Y] - 1;
		}
	}
	if (ans < 0) ans = ansx = ansy = 0;
	printf("%lld\n%d %d %d %d", ans, ansx, ansx, ansy, ansy);
}
2023/7/18 20:40
加载中...