Codeforces Round #331 (Div. 2) C. Wilbur and Points

強い人のコード見て気づいたけど、問題を取り違えていた。
が集合に含まれるならからまでの長方形領域に含まれるすべての点も集合に含まれるらしい。適当に散らばってると思ってた。適当に散らばってても解けるので、適当に散らばってると思って解説する。

問題

codeforces.com

問題概要

• 点の集合が与えられる
• が集合に含まれるならからまでの長方形領域に含まれるすべての点も集合に含まれる←この解説では無視
• 次の2つの条件を満たすように点を並び替える
  • 条件1：かつならば
  • 条件2：
• このような並び替え方が存在するならばその例をひとつ出力し、存在しないならNOと出力せよ

解法

まずの値で点を類別する。

を満たす点は直線上に存在する。

図を見ればわかるように、どの2点をとっても順序が定義されている。そのため各集合内では普通にソートができる。

あとは順に当てはめていくだけである。たとえばの場合、解の候補は

• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 

になる。

このようにして構成した列は解の候補であり、かつこれ以外の候補は作れない。そのため、この候補が条件1を満たせばそのまま出力し、満たさなければNOを出力すればいい。

条件1は番目の点より前にかつの点が存在しないと言い換えられる。いま番目の点を見ていて、グラフにはi番目までの点がプロットされている。緑色の領域に点が存在すれば、この候補は条件1を満たさない事がわかる。

地点におけるの最大値を持っておいて、より右側の範囲に高さ以上の値があるかどうかを判定すればいい。これはRMQ。

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;

struct RMQ {
    vector<int> mx;
    int size;
    RMQ(int n) {
        size = 1;
        while (size < n) size *= 2;
        mx.resize(size * 2, -1);
    }
    void update(int k, int v) {
        k += size - 1;
        chmax(mx[k], v);
        while (k > 0) {
            k = (k - 1) / 2;
            mx[k] = max(mx[k * 2 + 1], mx[k * 2 + 2]);
        }
    }
    int query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return -1;
        if (a <= l && r <= b) return mx[k];
        int x = query(a, b, k * 2 + 1, l, (l + r) / 2);
        int y = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return max(x, y);
    }
    int query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};

typedef pair<ll, ll> P;

int main() {
    int n;
    cin >> n;
    vector<ll> x(n), y(n), w(n);
    rep (i, n) scanf("%I64d %I64d", &x[i], &y[i]);
    rep (i, n) scanf("%I64d", &w[i]);
    map<ll, vector<P>> mp;
    rep (i, n) mp[y[i] - x[i]].emplace_back(x[i], y[i]);
    for (auto &kv : mp) {
        sort(kv.second.begin(), kv.second.end());
    }
    vector<P> ans;
    map<ll, int> now;
    rep (i, n) {
        if (now[w[i]] < mp[w[i]].size()) {
            ll ansx, ansy;
            tie(ansx, ansy) = mp[w[i]][now[w[i]]++];
            ans.emplace_back(ansx, ansy);
        }
    }
    if (ans.size() < n) {
        cout << "NO" << endl;
        return 0;
    }
    bool sorted = true;
    RMQ rmq(101010);
    rep (i, n) {
        ll tx = ans[i].first;
        ll ty = ans[i].second;
        ll maxx = rmq.query(tx, 101010);
        if (maxx >= ty) sorted = false;
        rmq.update(tx, ty);
    }
    if (!sorted) {
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl;
    rep (i, n) {
        printf("%I64d %I64d\n", ans[i].first, ans[i].second);
    }
    return 0;
}

感想

構築自体はすぐに思いついたけど順序判定に1時間近く悩んでしまった。