题解：CF1980F1 Field Division (easy version)

FiraCode · 2024-06-17 06:14:55 · 题解

这能绿？

由于 Alice 的路线不能往回走，所以他走的路线一定是这样的（红色是喷泉）：

那么我们发现，只有移走拐点且最小值变小后才会增加。

那么我们考虑维护后缀 \min，然后对于 x 相同的点，若哪一个 y 会使当前 \min 变小，那么移走这个点；若有多个 y 会使 \min 变小，那么取使 \min 变小最多的那个 y。

然后这一段路程就是当前 \min 乘这段路程的长度 x_i-x_{i-1}(x_i \not= x_{i-1})。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int T;
int n, m, k;
array<int, 3> a[200010];
int is[200010];

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= k; ++i) scanf("%d%d", &a[i][0], &a[i][1]), a[i][2] = i;

        sort(a + 1, a + 1 + k);
        ll minn = m + 1;
        ll sum = (minn - 1) * (n - a[k][0]);
        for (int i = k; i >= 1; --i) {
            int id = 0;
            if (a[i][1] < minn) id = a[i][2];
            minn = min(minn, 1ll * a[i][1]);
            while (i - 1 >= 1 && a[i - 1][0] == a[i][0]) {
                if (a[i - 1][1] < minn) id = a[i - 1][2];
                minn = min(minn, 1ll * a[i - 1][1]);
                --i;
            }

            sum += 1ll * (minn - 1) * (a[i][0] - a[i - 1][0]);

            is[id] = true;
        }

        printf("%lld\n", sum);
        for (int i = 1; i <= k; ++i) printf("%d ", (int)is[i]);
        puts("");
        for (int i = 1; i <= k; ++i) is[i] = 0;
    }
    return 0;
}