Submission

Score: 100

User: mthai

Problemset: ห้องสมุดเมือง 3M

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-04 21:56:46

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;

  vector<pair<long long, int>> events;
  long long total = 0;

  for (int i = 0; i < n; i++) {
    long long a, b;
    cin >> a >> b;
    events.push_back({a, +1});
    events.push_back({b, -1});
    total += b - a;
  }

  sort(events.begin(), events.end());

  // median อยู่ลำดับที่ floor(K/2) แบบ 1-indexed
  // แปลงเป็น 0-indexed: floor(K/2) - 1
  // แต่ถ้า K=1 ต้อง special case: floor(1/2) = 0 → ลำดับที่ 0 (1-indexed) หมายถึงตัวแรก
  // (0-indexed = 0)
  long long target;
  if (total <= 1) {
    target = 0;
  } else {
    target = total / 2 - 1;
  }

  long long count = 0;
  long long active = 0;

  for (int i = 0; i < (int)events.size(); i++) {
    long long pos = events[i].first;

    // รวม events ที่ตำแหน่งเดียวกัน
    long long delta = 0;
    int j = i;
    while (j < (int)events.size() && events[j].first == pos) {
      delta += events[j].second;
      j++;
    }

    long long nextPos = (j < (int)events.size()) ? events[j].first : pos + 1;
    active += delta;

    if (active > 0) {
      long long span = nextPos - pos;
      long long booksInSpan = active * span;

      if (count + booksInSpan > target) {
        long long remaining = target - count;
        long long offset = remaining / active;
        cout << pos + offset;
        return 0;
      }
      count += booksInSpan;
    }

    i = j - 1;
  }
}