Codeforces Round 857 (Div. 2) - D. Buying gifts (1800)

D. Buying gifts

$a_i$ 가 증가하는 순으로 정렬해보자.

현재 $i$ 에 대해 $a_i$ 를 첫 번째 사람이 가지는 가장 큰 숫자라고 하자.

만약 $j > i, b_j > a_i$ 인 $j$ 가 존재한다면 항상 $i+1 \sim n$ 번 째는 두 번째 사람에게 줘야하므로 $b_j-a_i$ 가 정답에 갱신되어야 한다.

그렇지 않다면 세 가지중 정답이 있다.

• $i+1 \sim n$ 에서 가장 큰 $b_j$ = $a_i$ 와 가장 가까운 수
• $1 \sim i-1$ 에서 가장 $a_i$ 와 가까운 $b_j$ (위아래로 가까운것 두개)

따라서 이를 multiset 으로 구현하면 정답은 $O(n \log n)$ 이다.

void solved() {
   int n;
   cin >> n;
   vector<pi> a(n);
   for (auto &[a, b]: a) cin >> a >> b;
   int ans = 2e15;
 
   sort(all(a));
   multiset<int> lo, hi;
   for (auto &[a, b]: a) hi.insert(b);
   for (int i = 0; i < n; i++) {
      hi.erase(hi.find(a[i].se));
 
      auto it = hi.rbegin();
      int cur_max = a[i].fi;
 
      if (it != hi.rend() && *hi.rbegin() >= cur_max) {
         mina(ans, abs(cur_max - *hi.rbegin()));
      } else {
         auto it = lo.upper_bound(cur_max);
         if (it != lo.end()) mina(ans, abs(cur_max - *it));
         if (it != lo.begin()) mina(ans, abs(cur_max - *(--it)));
         if (sz(hi)) mina(ans, abs(cur_max - *hi.rbegin()));
      }
      lo.insert(a[i].se);
   }
   cout << ans << endl;
}