Submission

Score: 0

User: sulinx

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-02-14 10:48:53

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

#define ll long long

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<pair<ll, ll>> ranges(n);
    ll sm = 0;
    
    for (auto &[l, r] : ranges) {
        cin >> l >> r;
        r--;
        sm += (r - l + 1);
    }
    
    if (sm == 1) return cout << ranges[0].first, 0;

    vector<pair<ll, int>> events;
    for (auto [l, r] : ranges) {
        events.push_back({l, 1});
        events.push_back({r + 1, -1});
    }
    sort(events.begin(), events.end());
    
    ll cur = 0, active = 0;
    ll target = (sm + 1) / 2;
    
    for (int i = 0; i < events.size(); ) {
        ll pos = events[i].first;
        
        while (i < events.size() && events[i].first == pos) {
            active += events[i].second;
            i++;
        }
        
        if (active == 0 || i == events.size()) continue;
        
        ll next_pos = (i < events.size()) ? events[i].first : pos + 1;
        ll len = next_pos - pos;
        
        if (cur + active * len >= target) {
            ll need = target - cur;
            cout << pos + (need - 1) / active;
            return 0;
        }
        
        cur += active * len;
    }
}