Submission

[PPPPP][PPPPP][PPPPPPPPPP]

Score: 100

User: Jibhong

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-22 19:53:35

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define int long long
typedef pair<int,bool> pib;
vector<pib>mem;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;
    cin>>n;
    int md=0;
    for(int i=0;i<n;++i){
        int u,v;
        cin>>u>>v;
        md+=v-u;
        mem.emplace_back(u,1);
        mem.emplace_back(v,0);
    }
    md/=2;
    sort(mem.begin(),mem.end());
//     cout<<md<<'\n';
    int last=0;
    int now=0;
    int cnt=0;
    int idx=0;
    int foundIdx;
    for(foundIdx=0;foundIdx<mem.size();++foundIdx){
        auto e=mem[foundIdx];
        //loop e until e.F is new use e only once
        if(last==e.F){
            if(e.S)++cnt;
            else --cnt;
            continue;
        }

        idx+=cnt*(e.F-last);
        bool iFoundIt=0;
        if(idx>=md){
            iFoundIt=1;
//             cout<<e.F<<' '<<e.S<<'\n';
        }
        if(iFoundIt)break;
        last=e.F;
        if(e.S)++cnt;
        else --cnt;

    }
//     cout<<mem[foundIdx].F<<' '<<cnt<<' '<<idx<<' '<<md<<' '<<foundIdx<<'\n';
    if(cnt==0)cout<<mem[foundIdx].F;
    else cout<<mem[foundIdx].F-(idx-md)/cnt-1;
    return 0;
}