Submission

Score: 0

User: NovemNotes

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-11 14:28:54

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

int n;
int sz=0;
vector<pair<int,int>> vp;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n;
    for(int i=0;i<n;i++){
        int a,b;cin >> a >> b;
        sz+=(b-a+1);
        vp.emplace_back(a,1);
        vp.emplace_back(b,-1);
    }
    sort(vp.begin(),vp.end(),[](const auto &x,const auto &y){
        if(x.first==y.first)return x.second < y.second;
        return x.first < y.first;
    });
    // for(auto &[x,y]:vp){
    //     cout << x << "\n";
    // }
    int target = sz/2;
    int sum=0;
    int l=-1,r=-1,sz=-1;
    for(int i=0;i<vp.size()-1;i++){
        sum += vp[i].second;
        if(sum<=0)continue;
        int first = vp[i].first;
        int last = vp[i+1].first-1;
        int range = vp[i+1].first - vp[i].first;
        // cout << first << " " << last << " " << range << " " << target << "\n";
        if(range*sum>=target){
            l=first;
            r=last;
            sz=sum;
            break;
        }else{
            target-=range;
        }
    }
    while(l<r){
        int mid = l+(r-l)/2;
        int rangeL = mid-l+1;
        if(rangeL*sz<target){
            l=mid+1;
            target-=(rangeL*sz);
        }else{
            r=mid-1;
        }
    }
    cout << l << "\n";
    // cout << l << " " << r << " " << sz << "\n";
    return 0;
}
/*
2
0 6
2 11
*/