社区讨论

68分求助,WA#1#4,码风较好,悬赏关注

P1856[IOI 1998 / USACO5.5] 矩形周长 Picture参与者 2已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lo1xlkl7
此快照首次捕获于
2023/10/23 04:38
2 年前
此快照最后确认于
2023/11/03 05:05
2 年前
查看原帖
CPP
#include <iostream>
#include <algorithm>
#include <cstring>
#define x1 x_1
#define y1 y_1
#define x2 x_2
#define y2 y_2
#define int long long
using namespace std;
const int N = 5e3 + 5;
const int M = 1e4 + 5;
int n, ans, last, cnt;

struct tree {
	int data, len;
}t[M<<3];

void pushup(int p, int l, int r) {
	if (l >= M*8 && r >= M*8) return;
	if (t[p].data) t[p].len = r-l+1;
	else t[p].len = t[p<<1].len + t[p<<1|1].len;
}

void updata(int p, int l, int r, int L, int R, int k) {
	if (L <= l && r <= R) {
		t[p].data += k;
		pushup(p, l, r);
		return;
	}
	int mid = l+r>>1;
	if (L <= mid) updata(p<<1, l, mid, L, R, k);
	if (mid < R) updata(p<<1|1, mid+1, r, L, R, k); 
	pushup(p, l, r);
}

struct node1 {
	int x;
	int y1, y2;
	int k;
}val1[N<<1];

struct node2 {
	int y;
	int x1, x2;
	int k;
}val2[N<<1];

bool operator<(const node1 & a, const node1 & b) {
	return a.x < b.x || (a.x == b.x && a.k > b.k);
}

bool operator<(const node2 & a, const node2 & b) {
	return a.y < b.y || (a.y == b.y && a.k > b.k);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=1; i<=n; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		int p = 1e4 + 1;
		x1 += p;
		y1 += p;
		x2 += p;
		y2 += p;
		val1[2*i-1] = (node1){x1, y1, y2, 1};
		val1[2*i] = (node1){x2, y1, y2, -1};
		val2[2*i-1] = (node2){y1, x1, x2, 1};
		val2[2*i] = (node2){y2, x1, x2, -1};
	}
	sort(val1+1, val1+2*n+1);
	for (int i=1; i<=2*n; i++) {
		updata(1, 1, 2*M-24, val1[i].y1, val1[i].y2-1, val1[i].k);
		ans += llabs(t[1].len - last);
		last = t[1].len;
	}
	sort(val2+1, val2+2*n+1);
	memset(t, 0, sizeof t);
	last = 0;
//	cout << ans << endl;
	for (int i=1; i<=2*n; i++) {
		updata(1, 1, 2*M-24, val2[i].x1, val2[i].x2-1, val2[i].k);
		ans += llabs(t[1].len - last);
		last = t[1].len;
	}
	cout << ans << endl;
	return 0;
} 

回复

5 条回复,欢迎继续交流。

正在加载回复...