错误提示: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;
}