莫名RE
查看原帖
莫名RE
550957
Anonymely楼主2024/1/13 18:04
#include <bits/stdc++.h>
using namespace std;

#define QwQ330AwA return 0
#define ll long long

const int N = 100005;
struct Node {
	int a, b, c, d;
	ll e;
	int op;
	int id;
	void print() {
		cout << a << ' ' << b << ' ' << c << ' ' << d << ' ' << e << '\n';
	}
} p[N], x[N], y[N];
int n;
ll f[N];
int mp[N], tot;

bool cmpa(Node u, Node v) {
	if (u.a != v.a) return u.a < v.a;
	if (u.b != v.b) return u.b < v.b;
	if (u.c != v.c) return u.c < v.c;
	return u.d <= v.d;	
}

bool cmpb(Node u, Node v) {
	if (u.b != v.b) return u.b < v.b;
	if (u.c != v.c) return u.c < v.c;
	if (u.d != v.d) return u.d < v.d;
	return u.a <= v.a;
}

bool cmpc(Node u, Node v) {
	if (u.c != v.c) return u.c < v.c;
	if (u.d != v.d) return u.d < v.d;	
	if (u.a != v.a) return u.a < v.a;
	return u.b <= v.b;	
}

ll t[N];
void upd(int x, ll w) {
	for (; x <= tot; x += x & (-x)) t[x] = max(t[x], w);
}
ll query(int x) {
	ll res = -1e18;
	for (; x; x -= x & (-x)) res = max(res, t[x]);
	return res;
}
void clear(int x) {
	for (; x <= tot; x += x & (-x)) t[x] = -1e18;
}

void cdq2(int l, int r) {
	if (l == r) return ;
	int mid = (l + r) / 2;
	cdq2(l, mid);
	for (int i = l; i <= r; i++) y[i] = x[i];
	sort(y + l, y + mid + 1, cmpc);
	sort(y + mid + 1, y + r + 1, cmpc);
	int L = l, R = mid + 1;
	for (int i = l; i <= r; i++) {
		if ((R > r) || (L <= mid && cmpc(y[L], y[R]))) {
			if (!y[L].op) upd(y[L].d, f[y[L].id]);
			L++;
		} else {
			if (y[R].op) f[y[R].id] = max(f[y[R].id], query(y[R].d) + y[R].e);
			R++;
		}
	}
	for (int i = l; i <= mid; i++) if (!y[i].op) clear(y[i].d);
	cdq2(mid + 1, r);	
}

void cdq1(int l, int r) {
	if (l == r) return ;
	int mid = (l + r) / 2;
	cdq1(l, mid);
	for (int i = l; i <= mid; i++) x[i] = p[i], x[i].op = 0;
	for (int i = mid + 1; i <= r; i++) x[i] = p[i], x[i].op = 1;
	sort(x + l, x + r + 1, cmpb);
	cdq2(l, r);
	cdq1(mid + 1, r);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> p[i].a >> p[i].b >> p[i].c >> p[i].d >> p[i].e;
	sort(p + 1, p + n + 1, cmpa);
	int cn = 0;
	for (int i = 1, j = 1; i <= n; i = j) {
		ll sum = 0;
		ll mx = -1e18;
		while (j <= n && p[j].a == p[i].a && p[j].b == p[i].b && p[j].c == p[i].c && p[j].d == p[i].d) mx = max(mx, p[j].e), sum += max(0ll, p[j].e), j++;
		p[++cn] = p[i];
		p[cn].e = (mx < 0 ? mx : sum);
		p[cn].id = cn;
	}
	n = cn;
	for (int i = 1; i <= n; i++) mp[++tot] = p[i].d;
	sort(mp + 1, mp + tot + 1);
	tot = unique(mp + 1, mp + tot + 1) - mp - 1;
	for (int i = 1; i <= tot; i++) t[i] = -1e18;
	for (int i = 1; i <= n; i++) p[i].d = lower_bound(mp + 1, mp + tot + 1, p[i].d) - mp, f[p[i].id] = p[i].e;
	cdq1(1, n);
	ll ans = -1e18;
	for (int i = 1; i <= n; i++) ans = max(ans, f[i]);
	cout << ans << '\n';
	QwQ330AwA;
}

Sub1 RE什么鬼

2024/1/13 18:04
加载中...