Submission

[P-SSS][SSSSS][SSSSSSSSSS]

Score: 0

User: Nakornrat

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-19 17:24:16

#include <iostream>
#include <vector>

using namespace std;

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 + 1);
    }
    return count;
}

int main() {
    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-1 << endl;
    return 0;
}