[ABC238] E - Range Sums
[Q] https://atcoder.jp/contests/abc238/tasks/abc238_e
A. UnionFindすれば、すぐのようだ。
N=3 Q=3
1 2 をuniteして
2 3 をuniteして
2 2 をuniteして、
1 と 3 が同じ集団ならYes。
そんな優れた解法は思いつかないので、無様に吐き出し法で解く。
1. {R, L} で降順sortする。Rの大きい値から処理する。
2. Rが同じ値の組み合わせについて。{ {5, 3}, {5, 2}, {5, 1} } の3本。
a) 1本目は基底として採用。{5,3} が基底。これで5-3まで網羅。
b) 2本目以降は、前Lで切断する。前L=3
{5, 2}は、切断して{3, 2}として扱う。前L=2
{5, 1}は、切断して{2, 1}として扱う。前L=1
3. 上位の基底から採用した場合、N~0までつながるならYes。
N=5 Q=4
5 5
5 4
5 3
5 2
1. ｛R, L-1} に降順ソートする。
5 4
5 3
5 2
5 1
2. R=5で走査。
a) 1本目
5 4 は基底として採用。前L=4
b) 2本目
5 3 は {4 3} に切断。// {前L 今L}
c) 3本目
5 2 は{3 2} に切断。
d) 4本目
5 1 は{2 1} に切断。
今時点で、以下の4本として扱う。
5 4 <= 基底
4 3
3 2
2 1
・R=4
4 3 だけなので基底。
・R=3
3 2 だけなので基底。
・R=2
2 1 だけなので基底。
3. 基底をつなげる。
5 4
4 3
3 2
2 1
ときれいにつながるが、5-0まで網羅できないのでNo。//L-1しているので、Lは0までつながりたい。実装
priority_queue<ll> P[200010];
int main() {
cincout();
ll N, Q;
cin >> N >> Q;
rep(i, Q) {
ll l, r;
cin >> l >> r;
--l;
P[r].push(l);
}
vector<pll> E; // 基底リスト
E.reserve(N);
ll now = N;
while (now > 0) {
ll nx = now;
while (!P[now].empty()) {
auto q = P[now].top();
P[now].pop();
if (nx == now) { // 1本目なら既定にする
E.push_back({now, q});
} else { // 2本目以降は切断して、P[前L]に辺追加
P[nx].push(q);
}
nx = q;
}
--now;
}
bool ok = true;
now = N;
for (auto e : E) { // 既定の上位から採用。N~0までつながるか
ll r = e.first;
ll l = e.second;
if (r > now)
continue;
else if (r == now)
now = l; // nowをL に更新
else if (r < now) { // now=3 r=2なら、3をとる基底がないのでNG
ok = false;
break;
}
}
if (now > 0) ok = false;
if (ok)
cout << "Yes" << endl;
else
cout << "No" << endl;
}