Codeforces Round #207 (Div. 1) A. Knight Tournament
解法
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 には返り値がある
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; }