Submission

[PPPPP][PPPPP][PPPPPPPPPP]

Score: 100

User: Nakornrat

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-19 18:23:02

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long int;
vector<pair<ll, ll>> a;
int n;
ll cala(ll mid){
    ll val = 0;
    for(int i=0;i<n;i++){
        if(mid<a[i].first)continue;
        val+=min(a[i].second-a[i].first, mid-a[i].first);
    }
    return val;
}
const ll inf = 1e12+7;
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    a.resize(n);
    ll sz = 0;
    ll l = inf, r = 0;
    for(int i=0;i<n;i++){
        cin>>a[i].first>>a[i].second;
        sz+=a[i].second-a[i].first;
        l = min(a[i].first, l);
        r = max(a[i].second, r);
    }
    ll medpos = sz/2-1;
    if(medpos-1<0)medpos = 0;
    ll mid;
    while(l<r){
        mid = l+(r-l)/2;
        if(cala(mid)<=medpos){
            l = mid+1;
        }else{
            r = mid;
        }
    }
    cout<<l-1<<endl;
}