社区讨论
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 条回复,欢迎继续交流。
正在加载回复...