[ABC327] F - Apples
[Q} F - Apples
考察
1. y軸を時間、x軸を座標の位置として、2次元グラフでリンゴを書いてみる。
T
...o...o.o.o..
o.....o.......
...o.......o..
.oo...o..oo...
...o....oo..o.
.o.o..o.o.o..o X
2. D*Wの長方形を当てはめてみて、最もリンゴを囲める数はいくつ?が解答になる。
3. 時間でsortして、しゃくとり法で時間を進めていく。
4. 遅延セグ木にりんごのデータを入れて入れて・・・、時間を進めたら、Dにおさまらない分は出して出して・・・をする。
5. 都度、もっともリンゴのとれる値を更新。
実装
int main() {
ll N, D, W;
cin >> N >> D >> W;
vector<pll> A;
rep(i, N) {
ll t, x;
cin >> t >> x;
A.emplace_back(t, x);
}
sort(all(A));
// 遅延セグ木
segment_tree seg(200020);
// しゃくとり
ll head = 0;
ll ans = 0;
rep(tail, N) {
auto [t, x] = A[tail];
while (head < N) { // 時間におさまらない限り取り出す
auto [tt, xx] = A[head];
if (t - tt >= D) {
seg.update(max(0LL, xx - W + 1), min(200010LL, xx + 1), -1);
++head;
} else
break;
}
// リンゴを挿入
seg.update(max(0LL, x - W + 1), min(200010LL, x + 1), 1); // update([L, R), addVal);
chmax(ans, seg.range_max(0, 200001));
}
cout << ans << endl;
}
https://atcoder.jp/contests/abc327/submissions/47268724
この記事が気に入ったらサポートをしてみませんか?