Codeforces Round #207 (Div. 1) A. Knight Tournament

問題

codeforces.com

解法

2 通り解法を紹介します。一つは vector を使う方法で, もうひとつは set を使う方法です。

vector を使う方は, next[i] = (i の次にトーナメントに残ってる人) というのを保持しておきます。最初は next[i] = i+1 ですが, 各クエリが来るごとに, i < x[i] なら next[i] = x[i] に, i > x[i] なら next[i] = next[r[i]] に更新します。

次に set を使う方です。set.erase(iterator) とやると, 返り値は消した iterator の次の iterator になることを利用して, もう負けていなくなった人はじゃんじゃん erase することで計算していきます。

練習会で set を使おうと思ったんですが, erase の仕様を知らなかったので iterator に関して怪しいコードを実装してバグり, 仕方なく vector を使いました…

まとめ

• set.erase には返り値がある

vector

const int MAXM = 300030;
int l[MAXM], r[MAXM], x[MAXM];
int ans[MAXM];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> l[i] >> r[i] >> x[i];
    vector<int> next(n+1);
    for (int i = 0; i <= n; i++) next[i] = i+1;
    for (int i = 0; i < m; i++) {
        int cur = l[i];
        while (cur <= r[i]) {
            int ncur = next[cur];
            if (cur < x[i]) {
                next[cur] = x[i];
                if (ans[cur] == 0) ans[cur] = x[i];
            } else if (cur > x[i]) {
                next[cur] = next[r[i]];
                if (ans[cur] == 0) ans[cur] = x[i];
            }
            cur = ncur;
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i];
        if (i < n) cout << " ";
    }
    cout << endl;
    return 0;
}

set

const int MAX = 300030;
int l[MAX], r[MAX], x[MAX];
int ans[MAX];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    set<int> S;
    for (int i = 1; i <= n; i++) S.insert(i);
    for (int i = 0; i < m; i++) {
        cin >> l[i] >> r[i] >> x[i];
        auto it = S.lower_bound(l[i]);
        for (; it != S.end() && *it <= r[i]; ) {
            if (*it != x[i]) {
                ans[*it] = x[i];
                it = S.erase(it);
            } else {
                it++;
            }
        }
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << endl;
    return 0;
}