Submission

[P-SSS][SSSSS][SSSSSSSSSS]

Score: 0

User: Pera

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-19 08:57:23

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

int main() {
    ios_base::sync_with_stdio(false);
    
    int n;
    cin >> n;

    vector<pair<int, int>> libraries(n);
    for (int i = 0; i < n; i++) {
        cin >> libraries[i].first >> libraries[i].second;
    }

    long long totalBooks = 0;
    for (int i = 0; i < n; i++) {
        totalBooks += libraries[i].second - libraries[i].first;
    }

    // The median is the (totalBooks / 2)-th book (0-indexed)
    long long medianIndex = totalBooks / 2;
    
    int low = 0;
    int high = 20000000;
    int median = -1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        // Count books with character count < mid
        long long countLess = 0;
        for (int i = 0; i < n; i++) {
            int x = libraries[i].first;
            int y = libraries[i].second;
            
            if (mid > x) {
                countLess += min(mid, y) - x;
            }
        }
        
        if (countLess <= medianIndex) {
            low = mid + 1;
        } else {
            median = mid - 1;
            high = mid - 1;
        }
    }
    
    cout << low - 2 << endl;
    
    return 0;
}