萌新刚学 OI,求助莫名其妙 RE
查看原帖
萌新刚学 OI,求助莫名其妙 RE
350270
CatFromMars楼主2024/10/20 17:28

如题,本地运行可以,在 luoguide 上测样例就会 RE,不知道为什么,求助 qwq

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5000 * 2;
struct seg {
	int x, yy1, yy2, tp;
} Q[N + 10];
bool cmp(seg &x, seg &y) {
    if(x.x != y.x) return x.x < y.x;
    else x.tp > y.tp;
}

int pos[N + 10], ptot = 0;

int add[N * 4 + 10], sum[N * 4 + 10];
int ls(int x) {
	return 2 * x;
}
int rs(int x) {
	return 2 * x + 1;
}
void push_tag(int now, int s, int t, int v) {
	add[now] += v;
	if(add[now]) sum[now] = pos[t + 1] - pos[s];
	else sum[now] = sum[ls(now)] + sum[rs(now)];
}
void push_up(int now, int s, int t) {
	if(add[now]) sum[now] = pos[t + 1] - pos[s];
	else sum[now] = sum[ls(now)] + sum[rs(now)];
}
void upd(int ql, int qr, int s, int t, int now, int v) {
	if(ql <= s && t <= qr) {
		push_tag(now, s, t, v);
		return ;
	}
	int mid = (s + t) >> 1;
	if(ql <= mid) upd(ql, qr, s, mid, ls(now), v);
	if(qr > mid) upd(ql, qr, mid + 1, t, rs(now), v);
	push_up(now, s, t);
}

int n, xx1[N + 10], yy1[N + 10], xx2[N + 10], yy2[N + 10];
int ans = 0;

void org() {
	ptot = 0;
	memset(add, 0, sizeof(add));
	memset(sum, 0, sizeof(sum));
	memset(pos, 0, sizeof(pos));
}
void forx() {
	org();
	for(int i = 1; i <= n; i++) {
		Q[i * 2 - 1] = (seg){xx1[i], yy1[i], yy2[i], 1};
		Q[i * 2] = (seg){xx2[i], yy1[i], yy2[i], -1};
		pos[++ptot] = yy1[i];
		pos[++ptot] = yy2[i];
	}
}
void fory() {
	org();
	for(int i = 1; i <= n; i++) {
		Q[i * 2 - 1] = (seg){yy1[i], xx1[i], xx2[i], 1};
		Q[i * 2] = (seg){yy2[i], xx1[i], xx2[i], -1};
		pos[++ptot] = xx1[i];
		pos[++ptot] = xx2[i];
	}
}
void work() {
	sort(pos + 1, pos + ptot + 1);
	int len = unique(pos + 1, pos + ptot + 1) - pos - 1;
	for(int i = 1; i <= 2 * n; i++) {
		Q[i].yy1 = lower_bound(pos + 1, pos + len + 1, Q[i].yy1) - pos;
		Q[i].yy2 = lower_bound(pos + 1, pos + len + 1, Q[i].yy2) - pos; 
	}

	sort(Q + 1, Q + 2 * n + 1, cmp);

	upd(Q[1].yy1, Q[1].yy2 - 1, 1, len, 1, Q[1].tp);
	int last = sum[1];
	ans += last;
	for(int i = 2; i <= 2 * n; i++) {
		upd(Q[i].yy1, Q[i].yy2 - 1, 1, len, 1, Q[i].tp);
		ans += abs(sum[1] - last);
		last = sum[1];
	}
}

signed main() {
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> xx1[i] >> yy1[i] >> xx2[i] >> yy2[i];

	forx(), work();
	fory(), work();
	cout << ans << endl;
}
2024/10/20 17:28
加载中...