[ABC225] E - フ

[Q] https://atcoder.jp/contests/abc225/tasks/abc225_e
・そもそもフじゃなかった。

Q. フ？
A. 
____
   |
   |

・座標圧縮 + セグ木で500msくらいでした。

・問題の読み替え
範囲がたくさん与えられたときに、範囲の重複なくできるだけ多く取るにはどうすればいいか、という読み替えができる。

Q. たとえばこんな問題。

要素が5個あって、重複せずに何要素とれるか。
1 2
2 3
3 4
4 5
2 6

これは、
1--2
   2--3
      3--4
         4--5
   2----------6

1,2,3,4の4本をとればよさそう。

Q. どうやって求める？
A. セグ木。

1. 右端の大きいものから処理していく。
1) 2 6
   2----------6

右端 6 以上で取れる最大要素は、0個。
ここまでで、自分を含めてとれる要素数は 0+1 = 1個。
左端 seg[2] = 1 をメモ。

2) 4 5

         4--5
  [1]        [0]
   2----------6

右端 5 以上で取れる最大要素は、0個。
ここまでで、自分を含めてとれる要素数は 0+1 = 1個。
左端 seg[4] = 1 をメモ。


3) 3 4

      3--4
        [1]
         4--5
  [1]          [0]
   2----------6

右端 4 以上で取れる最大要素は、1個。
ここまでで、自分を含めてとれる要素数は 1+1 = 2個。
左端 seg[3] = 2 をメモ。

4) 2 3

   2--3
     [2]
      3--4
        [1]
         4--5
  [1]          [0]
   2----------6

右端 3 以上で取れる最大要素は、2個。
ここまでで、自分を含めてとれる要素数は 2+1 = 3個。
左端 seg[2] = 3 をメモ。

5) 1 2

1--2
  [3]
   2--3
     [2]
      3--4
        [1]
         4--5
  [1]          [0]
   2----------6

右端 2 以上で取れる最大要素は、3個。
ここまでで、自分を含めてとれる要素数は 3+1 = 4個。
左端 seg[1] = 4 をメモ。


segの最大値が4なので 4本。

1. それぞれのフについて、傾きの小 ~ 大を、範囲と読み換えることができる。
2. doubleの範囲そのままだとできないので、座標圧縮で整数化する。
3. 整数範囲が求まれば、最大値が大きいものから順番にセグ木処理すればよさそう。

実装

ld X[200010];
ld Y[200010];

int main(){
 cincout();
 
 ll N;
 cin >> N;
 rep(i, N){
   ll x, y;
   cin >> x >> y;
   X[i] = x;
   Y[i] = y;
 }
 
 vector<ld> V;
// 範囲の最小(d2) ~ 最大(d1)を求める。
 rep(i, N){
   ld x = X[i];
   ld y = Y[i];
   ld d1 = -oo;
   ld d2 = oo;
   
   // xy
   chmax(d1, y/x);
   chmin(d2, y/x);
   
   // x-1, y
   if (x>0){
     chmax(d1, y/(x-1));
     chmin(d2, y/(x-1));
   }
   else if (x==0){
     chmax(d1, oo);
   }
   
   // x, y-1
   chmax(d1, (y-1)/x);
   chmin(d2, (y-1)/x);
   
   V.push_back(d1);
   V.push_back(d2);
 }

 // 座圧
 comp<ld>(V);

// 範囲を、右端の大きい順に並べたい。pair<ll, ll>で管理。
 vector<pll> C; // sortしたい
 
 rep(i, N){ // V = {d1, d2, d1, d2...}
   ll v1=V[i*2];
   ll v2=V[i*2+1];
   C.push_back({v1, v2});
 }
 sort(all(C), greater<pll>());

// セグ木
 RangeMax Z;
 Z.init(400010); // N*2 要素まで入りうる
 Z.update(400005, 0);
 ll ans = 0;
 rep(i, N){
   ll up = C[i].first;
   ll down = C[i].second;
   
   ll high = Z.query(up, 400009);
   Z.update(down, high + 1); // id, val
   chmax(ans, high+1);
 }
 
 cout << ans << endl;
}

https://atcoder.jp/contests/abc225/submissions/26937252