Submission

[PPPPP][PPPPP][PPPPPPPPPP]

Score: 100

User: qwerty

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-15 21:10:43

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

#define ll long long
vector<ll> start;
vector<ll> ending;
ll len = 0;
ll l = 0, r = 2e9;
bool check(ll mid, int n) {
    ll val = 0;
    for (int i = 1 ; i <= n ; i++) {
        if (mid < start[i]) continue;
        if (mid >= ending[i]) val+=ending[i]-start[i]+1;
        else val+=mid-start[i]+1;
    }
    if (val <= max(len/2 - 1, 0LL)) return true;
    return false;
}

int main() {
    ll n;
    cin >> n;
    start.resize(n+1);
    ending.resize(n+1);
    for (ll i = 1 ; i <= n ; i++) {
        ll a, b;
        cin >> a >> b;
        start[i] = a;
        b--;
        ending[i] = b;
        len+=b-a+1;
    }

    while (l<r) {
        ll mid = (l+r)/2;
        if (check(mid, n)) {
            l = mid+1;
        } else {
            r = mid;
        }
    }
    cout << l;
}