扫描线+线段树90ptsWA#8求助
  • 板块P1382 楼房
  • 楼主XuHenry
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/12/21 12:35
  • 上次更新2024/12/21 16:24:22
查看原帖
扫描线+线段树90ptsWA#8求助
1402161
XuHenry楼主2024/12/21 12:35

错误提示:wrong answer On line 21837 column 12, read 0, expected 4.

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1e5;
int n;
struct elem {
	int x, h;
	bool in;
} a[N << 1];
bool operator<(const elem &_a, const elem &_b) { return _a.x < _b.x; }
int tot = 1, q[N + 1];
struct node {
	int l, r, val;
	int cnt, sum;
} tr[N << 3];
#define li i << 1
#define ri i << 1 | 1
#define now tr[i]
#define lson tr[li]
#define rson tr[ri]
void build(const int &i, const int &l, const int &r) {
	now.l = l, now.r = r, now.val = q[r] - q[l - 1];
	if(l == r) return;
	const int mid = (l + r) >> 1;
	build(li, l, mid);
	build(ri, mid + 1, r);
}
void pushup(const int &i) {
	now.sum = (now.cnt ? now.val : lson.sum + rson.sum);
}
void insert(const int &i, const int &l, const int &r, const bool &in) {
	if(l <= now.l && now.r <= r) {
		in ? ++now.cnt : --now.cnt;
		pushup(i);
		return;
	}
	if(l <= lson.r) insert(li, l, r, in);
	if(r >= rson.l) insert(ri, l, r, in);
	pushup(i);
}
int ans = 1;
struct answer {
	int x, p;
} aq[N << 1 | 1];
void smin(int &x, const int &y) { if(x > y) x = y; }
void smax(int &x, const int &y) { if(x < y) x = y; }
int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >>n;
	for(int i = 0; i < n; ++i) {
		int h, l, r;
		cin >>h >>l >>r;
		a[li] = {l, h, true}, a[ri] = {r, h, false};
		q[tot++] = h;
	}
	n <<= 1;
	sort(a, a + n);
	sort(q, q + tot);
	tot = unique(q, q + tot) - q;
	build(1, 1, tot - 1);
	aq[0].x = INT_MIN;
	for(int i = 0; i < n; ++i) {
		const int h = lower_bound(q, q + tot, a[i].h) - q;
		insert(1, 1, h, a[i].in);
		if(tr[1].sum != aq[ans - 1].p) {
			if(a[i].x == aq[ans - 1].x)
				aq[ans - 2].p > aq[ans - 1].p ? 
					smin(aq[ans - 1].p, tr[1].sum) :
					smax(aq[ans - 1].p, tr[1].sum);
			else aq[ans++] = {a[i].x, tr[1].sum};
		}
	}
	cout <<((ans - 1) << 1) <<'\n';
	for(int i = 1; i < ans; ++i)
		cout <<aq[i].x <<' ' <<aq[i - 1].p <<'\n' <<aq[i].x <<' ' <<aq[i].p <<'\n';
	return 0;
}
2024/12/21 12:35
加载中...