Submission

Score: 100

User: kittipos

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

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-04 15:56:48

#include <iostream>
#include <limits>
#include <vector>

using namespace std;

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

  int n;
  cin >> n;

  vector<pair<int, int>> books;

  books.resize(n);

  int smallest = numeric_limits<int>::max();
  int biggest = 0;
  int page_count = 0;
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    books[i].first = a;
    books[i].second = b;

    smallest = min(smallest, a);
    smallest = min(smallest, b);

    biggest = max(biggest, a);
    biggest = max(biggest, b);

    page_count += b - a;
  }

  int left = smallest - 1;
  int right = biggest - 1;
  int target = page_count / 2;
  // cout << "target: " << target << endl;
  while (left + 1 < right) {
    int center = (right + left) / 2;
    int center_count = 0;
    for (int i = 0; i < books.size(); i++) {
      if (center < books[i].first) {
        continue;
      } else if (center < books[i].second) {
        center_count += center - books[i].first + 1;
      } else {
        center_count += books[i].second - books[i].first;
      }
    }

    // cout << "count: " << center_count << endl;

    if (center_count >= target) {
      right = center;
    } else {
      left = center;
    }

    // if (center_count < target) {
    //     left = center;
    //     right = center;
    // } else {
    // }
  }

  cout << right;

  return 0;
}