Submission

Score: 100

User: s0m30n3

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-01-26 20:22:55

// Binary Search
#include<iostream>
#include<vector>
#include<cmath>
#include <climits>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<pair<int ,int>> range;
    int ma=0;
    int mi=INT_MAX;
    long long K=0;
    for(int i=0;i<n;i++){
        int x,y;
        cin >> x >> y;
        ma = max(ma, y);
        mi = min(mi,x);
        range.push_back({x,y});
        K += (long long)(y - x);
    }
    int left=mi;
    int right=ma;
    int target = floor(K/2);
    int answer=0;
    while(left<=right){
        int mid = left + (right-left)/2;
        int test=0;
        for (auto p : range) {
            int u = p.first;
            int v = p.second;
            long long cnt = min(v, mid + 1) - u;
            if (cnt > 0) test += cnt;
        }        
        if(test >= target){
           right=mid-1;
           answer=mid;
        }
        else{
           left=mid+1;
        }
    }
    cout << answer;
}