Submission

Score: 0

User: Quinruj

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-11-08 17:38:33

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;cin>>n;
    vector<pll> v;
    for (int i = 0;i<n;i++){
        int l,r;cin>>l>>r;
        r--;
        bool found = false;
        for (auto &[vl,vr] : v){
            if (l <= vr && r >= vr){
                vr = r;
                found = true;
                break;
            }
            else if (r >= vl && l <= vl){
                vl = l;
                found = true;
                break;
            }
        }
        if (!found) v.emplace_back(l,r);
    }
    sort(v.begin(),v.end());
    vector<ll> sz(v.size()+1);
    for (int i = 1;i<sz.size();i++) {
        int n = v[i-1].second-v[i-1].first+1;
        sz[i] = sz[i-1]+n;
        // cout << sz[i] << ' ';
    }
    ll mx = sz[sz.size()-1];
    ll fi = mx/2;
    auto it = upper_bound(sz.begin(),sz.end(),fi)-sz.begin();
    fi = fi - sz[it-1];
    cout << v[it-1].first + fi - 1;
}