WA 33pts 求调(错误点全部输出负数)
查看原帖
WA 33pts 求调(错误点全部输出负数)
700558
williamwei楼主2024/7/21 19:13

如题,错误的点全输出了负数。

提交记录: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太大了,调不出来,求调

2024/7/21 19:13
加载中...