如题,错误的点全输出了负数。
提交记录:https://www.luogu.com.cn/record/167622586
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
const int maxn = 2e5 + 10;
int n, m, m1, m2, ans, c[maxn], b1[maxn], b2[maxn];
vector<tuple<int, int, int> > e[maxn];
#define ID(x, a, l) (lower_bound(a + 1, a + l + 1, x) - a)
void add(int x, int v) {
for (; x <= m2; x += x & -x) c[x] = max(c[x], v);
}
int getmax(int x) {
int res = 0; for (; x; x -= x & -x) res = max(res, c[x]);
return res;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
vector<tuple<int, int, int, int> > g(m);
for (auto& [sx, sy, ex, ey] : g) {
cin >> sx >> sy >> ex >> ey;
b1[++m1] = sx; b1[++m1] = ex;
b2[++m2] = sy; b2[++m2] = ey;
}
sort(b1 + 1, b1 + m1 + 1); sort(b2 + 1, b2 + m2 + 1);
m1 = unique(b1 + 1, b1 + m1 + 1) - b1 - 1;
m2 = unique(b2 + 1, b2 + m2 + 1) - b2 - 1;
for (auto [sx, sy, ex, ey] : g)
sx = ID(sx, b1, m1), sy = ID(sy, b2, m2),
ex = ID(ex, b1, m1), ey = ID(ey, b2, m2),
e[ex].emplace_back(ey, sx, sy);
for (int ex = 1; ex <= m1; ex++) {
sort(e[ex].begin(), e[ex].end());
for (auto [ey, sx, sy] : e[ex]) {
int val = getmax(sy) + b1[ex] + b2[ey] - b1[sx] - b2[sy];
ans = max(ans, val); add(ey, val);
}
}
cout << (n << 1) - ans << '\n';
return 0;
}
我有hack,但是hack太大了,调不出来,求调