Submission

Status:
[PPPP-][SSSSS][SSSSSSSSSS]

Score: 0

User: Nakornrat

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-19 17:17:59

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int n;
vector<pair<int, int>> books;


long long countBooks(int val) {
    long long count = 0;
    for (const auto& range : books) {
        if (range.first > val) continue;
        count += min(range.second - range.first, val - range.first);
    }
    return count;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n;
    
    int minX = 2e7, maxY = 0;
    long long total_books = 0;
    
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        books.emplace_back(x, y);
        minX = min(minX, x);
        maxY = max(maxY, y);
        total_books += (y - x);
    }

    long long median_pos = total_books / 2 - 1;
    int left = minX, right = maxY - 1, answer = minX;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (countBooks(mid) >= median_pos) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << answer << endl;
    return 0;
}