Submission

Score: 20

User: Kx

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-16 20:28:12

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

int n, res = 0;
vector<pair<int, int>> p, g;

void getp(int l, int r) {
    if(g.empty()) g.push_back({l, r});
    
    for(auto &x : g) {
        if(l >= x.first && r <= x.second) {
            return;
        } else if(l >= x.first && r >= x.second) {
            x.second = r;
        } else if(l <= x.first && r <= x.second) {
            x.first = l;
        } else if(l <= x.first && r >= x.second) {
            x.first = l, x.second = r;
        } else {
            g.push_back({l, r});
        }
    }
    
    return;
}

int main() {
    cin >> n;
    p.resize(n);
    
    for(int i = 0; i < n; ++i) {
        cin >> p[i].first >> p[i].second;
    }
    
    sort(p.begin(), p.end());
    
    for(auto x : p) {
        getp(x.first, x.second - 1);
    }
    
    int sz = 0;
    for(auto x : g) {
        sz += (x.second - x.first + 1);
    }
    
    sz /= 2;
    
    for(auto x : g) {
        int cur_sz = x.second - x.first + 1;
        if(sz <= cur_sz && x.second - x.first > 0) {
            res = x.first + sz - 1;
            break;
        } else if(sz <= cur_sz && n == 1){
            res = x.first + sz;
            break;
        } else {
            sz -= cur_sz;
        }
    }
    
    cout << res << '\n';
    
    return 0;
}