ABC 377
Table of Contents
https://atcoder.jp/contests/abc377
A. Rearranging ABC
https://atcoder.jp/contests/abc377/tasks/abc377_a
B. Avoid Rook Attack
https://atcoder.jp/contests/abc377/tasks/abc377_b
C. Avoid Knight Attack
https://atcoder.jp/contests/abc377/tasks/abc377_c
D. Many Segments 2
https://atcoder.jp/contests/abc377/tasks/abc377_d
自力 AC.
考えられる区間 $\binom{M}{2} + M$ 個の中から、与えられた区間を完全に含むようなものの個数を引くことを考える。
まず、2つの区間 $[L_i, R_i], [L_j, R_j]$ に対して $L_i = L_j \wedge R_i < R_j$ となるようなものがあるとき、 $[L_j, R_j]$ を無視しても答えに影響はない。
よって $l = L_i$ となるような $i$ に対して $R_i$ の最小値だけを残すようにする。
左端を $l$ としたとき、区間の左端が $l$ 以降のものの中で右端が最小のものの座標を $r_{\min}$ とすると $M - r_{\min} + 1$ 個の区間は 何かしらの区間を完全に含むことになるのでその個数を引く。 これを $l = 1 \sim M$ に対して計算をする。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, M;
cin >> N >> M;
vll v(M + 1, INF);
rep(i, N) {
ll l, r;
cin >> l >> r;
chmin(v[l], r);
}
multiset<ll> right;
rep2(i, 1, M + 1) {
if (v[i] == INF) continue;
right.insert(v[i]);
}
ll ans = M * (M - 1) / 2 + M;
int i = 1;
while (right.size()) {
auto it = right.begin();
ans -= M - *it + 1;
if (v[i] != INF) {
auto erase_it = right.lower_bound(v[i]);
right.erase(erase_it);
}
i++;
}
cout << ans << endl;
}
E. Permute K times 2
https://atcoder.jp/contests/abc377/tasks/abc377_e
F. Avoid Queen Attack
https://atcoder.jp/contests/abc377/tasks/abc377_f