[ARC129] B - Range Point Distance
[Q] https://atcoder.jp/contests/arc129/tasks/arc129_b
AよりBのほうが簡単かもしれない。
1. Lの最大値と、Rの最小値を常に更新すればいい。
2. Lmax - Rminで法則がみつかる。
Q.
3
1 3
2 4
5 6
1.) 1 3 を考える。
1~3 が 0 で、それ以外は距離がスコアになっているので、こう。
0 1 2 3 4 5 6 7
===============
1 0 0 0 1 2 3 4 // Lmax = 1, Rmin = 3
最小は 0
2.)2 4 を考える。
0 1 2 3 4 5 6 7
===============
1 0 0 0 1 2 3 4 // Lmax = 1, Rmin = 3
2 1 0 0 0 1 2 3 // Lmax = 2, Rmin = 3
---- max ------
2 1 0 0 1 2 3 4
最小は 0
3.)5 6 を考える。
0 1 2 3 4 5 6 7
===============
1 0 0 0 1 2 3 4 // Lmax = 1, Rmin = 3
2 1 0 0 0 1 2 3 // Lmax = 2, Rmin = 3
5 4 3 2 1 0 0 1 // Lmax = 5, Rmin = 3
---- max ------
5 4 3 2 1 2 3 4
^ ^
[3] [5]
Q. 最小は 1 だけど、どう求める？
A.
ll dif = Lmax - Rmin = 5-3 = 2
これは、maxをとった配列のindex
max[Lmax] = max[5] = 2
max[Rmin] = max[3] = 2
と合致する。
LmaxとRminの中間に近づくほど値が減少する。
その減少度合いは、
ll dis = dif/2 = 1
で求まる。
ll ans = dif - dis = 2 - 1 = 1実装
int main(){
cincout();
ll N;
cin >> N;
ll up = oo;
ll down = -oo;
rep(n, N){
ll L, R;
cin >> L >> R;
chmax(down, L);
chmin(up, R);
if (down <= up) cout << 0 << endl;
else{
ll dif = down - up;
ll ans = dif - dif/2;
cout << ans << endl;
}
}
}