Submission

Score: 100

User: sulinx

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

Language: cpp

Time: 0.003 second

Submitted On: 2026-02-14 11:04:59

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

int main() {
    int n;
    cin >> n;
    
    vector<pair<int, int>> ranges;
    int globalMax = 0;
    int globalMin = INT_MAX;
    long long totalPoints = 0;
    
    for (int i = 0; i < n; i++) {
        int start, end;
        cin >> start >> end;
        
        globalMax = max(globalMax, end);
        globalMin = min(globalMin, start);
        ranges.push_back({start, end});
        
        totalPoints += (long long)(end - start);
    }
    
    long long targetCount = totalPoints / 2;
    
    int left = globalMin;
    int right = globalMax;
    int medianValue = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        long long pointsUpToMid = 0;
        for (auto& range : ranges) {
            int start = range.first;
            int end = range.second;
            
            long long count = min(end, mid + 1) - start;
            if (count > 0) {
                pointsUpToMid += count;
            }
        }
        
        if (pointsUpToMid >= targetCount) {
            medianValue = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    cout << medianValue << endl;
    
    return 0;
}