Submission

[PPPPP][PPPPP][PPPPPPPPPP]

Score: 100

User: Pera

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-19 08:59:30

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<pair<int,int>> libs(n);
    int minVal = 20000000, maxVal = 0;
    for (int i = 0; i < n; i++){
        cin >> libs[i].first >> libs[i].second;
        minVal = min(minVal, libs[i].first);
        maxVal = max(maxVal, libs[i].second); // note: books have counts up to (Yi-1)
    }
    
    long long total = 0;
    for (int i = 0; i < n; i++){
        total += (long long)libs[i].second - libs[i].first;
    }
    
    // define median index in 0-indexed order.
    // As per the problem, if there are K books, the median is the book at position ⌊K/2⌋ (1-indexed)
    // which is index (⌊K/2⌋ - 1) in 0-indexed order (unless there's only one book).
    long long t = total / 2;
    long long target = (t > 0 ? t - 1 : 0);
    
    auto countLess = [&](int x) -> long long {
        long long cnt = 0;
        for (int i = 0; i < n; i++){
            int L = libs[i].first, R = libs[i].second;
            if(x > L) {
                cnt += min(x, R) - L;
            }
        }
        return cnt;
    };
    
    int low = minVal, high = maxVal;
    int ansCandidate = low; // if no book found, answer is minVal
    while(low <= high){
        int mid = low + (high - low) / 2;
        long long cnt = countLess(mid);
        if(cnt > target){
            ansCandidate = mid;  // this mid makes cumulative count exceed target
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    
    cout << ansCandidate - 1 << "\n";
    
    return 0;
}