Submission

Score: 0

User: C12

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

Language: cpp

Time: 0.003 second

Submitted On: 2025-11-05 01:38:56

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

#define f first
#define s second
#define pii pair<ll,ll>
#define piii pair<ll,pii>
#define ll long long
#define mp make_pair
 
#define mpiii(a,b,c) make_pair(a,make_pair(b,c));
ll mod = 1000000007;

void solve(){
    ll n;

    cin >> n;

    vector<pii>v(n);

    ll x,y,sumAll = 0;

    ll now,sum = 0,st;

    for(int i = 0;i < n;i++){
        cin >> x >> y;
        v[i] = mp(x,y);
        sumAll += y-x;
    }

    if(n == 1){
        if((y-x) & 1) y--;
        cout << ((x+y-1)/2);
        return;
    }

    sort(v.begin(),v.end());

    int i = 0;
    int lastAct;

    priority_queue<ll, vector<ll>, greater<ll>>pq;

    while(sum < sumAll/2){
        st = pq.size();
        if(pq.empty()){
            pq.push(v[i].s);
            now = v[i].f;
            lastAct = 0;
            i++;
        }
        else if(pq.top() > v[i].f){
            sum += (v[i].f - now) * st;
            now = v[i].f;
            pq.push(v[i].s);
            lastAct = 0;
            i++;
        }
        else if(pq.top() <= v[i].f){
            sum += (pq.top() - now) * st;
            now = pq.top();
            lastAct = 1;
            pq.pop();
        }
        // cout << now << ' ' << sum << ' ' << sumAll << ' ' << pq.top() << ' ' << pq.size() << ' ' << i  << ' ' << lastAct << '\n';
    }

    now -= lastAct;
    if(sum >= sumAll/2){
       now -= ceil((float)(sum - (sumAll/2))/st);
    }
    
    cout << now;
    return;

}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll q;
 
    // cin >> q;

    // while(q--) 
    
    solve();

    return 0;
}