Submission

[PP-SS][SSSSS][SSSSSSSSSS]

Score: 0

User: mydKN

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-23 13:55:16

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

struct stc{
    ll val, state;
    bool operator<(const stc& a) const{
        if(val == a.val) return state > a.state;
        return val < a.val;
    }
};

ll n;
vector<stc> vec;
ll cnt;
ll med;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(ll i=0;i<n;++i){
        ll s, t;
        cin >> s >> t;
        vec.push_back({s, 1});
        vec.push_back({t, -1});
        med += (t-s);
    }
    med /= 2;
    sort(vec.begin(), vec.end());
    for(ll i=0;i<vec.size()-1;++i){
        if(med <= 0) break;
        cnt += vec[i].state;
        ll tmp = (vec[i+1].val - vec[i].val) * cnt;
        if(med <= tmp){
            ll pos = med - 1;
            ll dist = pos / cnt;
            ll book = vec[i].val + dist;
            cout << book << "\n";
            return 0;
        }
        med -= tmp;
    }
}