Atcoder Grand Contest 013 F. Two Faced Cards

Atcoder Grand Contest 013 F. Two Faced Cards

F - Two Faced Cards

解法

解法がかなりきれいで、よい問題だと思いました。

editorialの英語版がわかりやすかったので、そこに書かれているように実装しました。

まず定石ですが、$c$ はソートして座圧し、$c$ 以外の数値は $c$ に対する相対値として座圧しておきます。

この問題は、二つの数列 $p, q$ があって、それらをうまく並び替えてすべての $i$ について $p_i \leq q_i$ が成り立つようにできるかをどのように判定するかが鍵になっています。

自明なやり方としては各数列をソートして順に見ていけばよいのですが、計算量がやばい上に、要素の変更に対して動的に判定できません。そこで、次のような判定をします。

数値に関する配列を用意して、最初すべてを $0$ とします。まず各 $i$ に対して区間 $[p_i, n]$ に $1$ を足します。そのあと、各 $i$ に対して区間 $[q_i, n]$ に $-1$ を足します。この結果すべての要素が $0$ 以上であれば条件を満たします。

これで動的に裏表を変えることができるようになりました。つまり、最初はすべて表にしたと仮定して、そのように区間を塗っておいて、数字が $a$ から $b$ に変わる（ただし $a > b$ でないと変えるメリットがありません）ときは区間 $[b, a)$ に $1$ を加算すればよいです。

最後に一枚だけ加えることができることを考慮すると、配列の各値は最低でも $-1$ 以上でなければいけません。よってとりあえずすべてが $-1$ 以上になるまで、右から貪欲に区間を使って加算していきます。

最後の一枚が数 $x$ だとすると（裏表両方試せば良い）、最後に足せる区間はやはり $[x, n)$ なので、区間 $[0, x)$ をすべて $0$ 以上にするために必要な区間の数をすべての $x$ について計算すれば、どんなクエリが来ても答えることができます。これは左から $-1$ をつぶすように区間を選んでいくことで計算できます。

実装の注意としては、実際に区間加算をするのは難しいため、例えば左から見て行く場合は、実際の区間に加算するわけではなく、[今いる位置, 区間の右端)に加算をするようにしてよいです。これなら累積和をとるだけで計算可能です。ただし、実際に配列の値がどうなったのかを知るためには使った区間を保存しておかなければいけません。

実装

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int main() {
        int n;
        scanf("%d", &n);
        vector<int> a(n), b(n);
        for (int i = 0; i < n; i ++) scanf("%d%d", &a[i], &b[i]);
        vector<int> c(n + 1);
        for (int i = 0; i < n + 1; i ++) scanf("%d", &c[i]);
        sort(c.begin(), c.end());
        auto convert = [&](int x) {
                auto d = lower_bound(c.begin(), c.end(), x) - c.begin();
                return d;
        };
        vector<vector<int>> g(n + 1);
        for (int i = 0; i < n; i ++) {
                a[i] = convert(a[i]);
                b[i] = convert(b[i]);
                if (a[i] > b[i]) { 
                        g[a[i] - 1].push_back(b[i]);
                }
        }
        vector<int> sum(n + 1, 0);
        for (int i = 0; i < n + 1; i ++) sum[i] --;
        for (int i = 0; i < n; i ++) sum[a[i]] ++;
        vector<int> realsum = sum;
        vector<int> revsum(n + 1, 0);
        for (int i = 0; i < n; i ++) sum[i + 1] += sum[i];
        revsum[n] = sum[n];
        for (int i = n; i > 0; i --) revsum[i - 1] = sum[i - 1] - sum[i];
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> seg;
        vector<pair<int, int>> used;
        bool ok = true;
        for (int i = n; i >= 0; i --) {
                if (i < n) revsum[i] += revsum[i + 1];
                for (auto to : g[i]) {
                        seg.emplace(to, i);
                }
                while (revsum[i] < -1 && !seg.empty()) {
                        pair<int, int> get = seg.top();
                        seg.pop();
                        int left = get.first;
                        revsum[i] ++;
                        if (left > 0) revsum[left - 1] --;
                        used.push_back(get);
                }
                if (revsum[i] < -1) {
                        ok = false;
                }
        }
        vector<vector<int>> rest(n + 1);
        while (!seg.empty()) {
                pair<int, int> get = seg.top();
                seg.pop();
                rest[get.first].push_back(get.second + 1);
        }
        for (auto it : used) {
                realsum[it.first] ++;
                realsum[it.second + 1] --;
        }
        int necessary = (int) used.size();
        priority_queue<pair<int, int>> seg2;
        vector<int> cnt(n + 1);
        for (int i = 0; i < n + 1; i ++) {
                if (i > 0) { 
                        realsum[i] += realsum[i - 1];
                        cnt[i] += cnt[i - 1];
                }
                for (auto to : rest[i]) {
                        seg2.emplace(to, i);
                }
                while (realsum[i] < 0 && !seg2.empty()) {
                        pair<int, int> get = seg2.top();
                        seg2.pop();
                        int right = get.first;
                        realsum[i] ++;
                        realsum[right] --;
                        cnt[i] ++;
                }
                if (realsum[i] < 0) {
                        cnt[i] = 1 << 30;
                }
        }
        int q;
        scanf("%d", &q);
        while (q --) {
                int d, e;
                scanf("%d%d", &d, &e);
                if (!ok) {
                        printf("%d\n", -1);
                        continue;
                }
                d = convert(d);
                e = convert(e);
                int res1 = (d == 0 ? 0 : cnt[d - 1]);
                int res2 = (e == 0 ? 1 : cnt[e - 1] + 1);
                int res = min(res1, res2);
                int ans = n - necessary - res + 1;
                if (ans < 0) printf("%d\n", -1);
                else printf("%d\n", ans);
        }                                      
        return 0;
}