Submission

[PP-SS][SSSSS][SSSSSSSSSS]

Score: 0

User: Pera

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-24 21:07:33

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

long long countbooklessthanmid(vector<pair<long long, long long>>& libs, long long mid) {
    long long count = 0;
    for (auto& lib : libs) {
        if (lib.first <= mid) {
            count += min(mid + 1, lib.second) - lib.first;
        }
    }
    return count;
}

int main() {
    long long n; cin >> n;
    vector<pair<long long, long long>> libs(n);
    long long books{0};
    for (long long i = 0; i < n; i++) {
        long long x, y;
        cin >> x >> y;
        books += y - x;
        libs[i].first = x;
        libs[i].second = y;
    }

    long long medianidx = books / 2;
    long long low = 0;
    long long high = 20000000;
    long long result{};

    while (low <= high) {
        long long mid = (low + high) / 2;

        if (countbooklessthanmid(libs, mid) >= medianidx) {
            high = mid - 1;
            result = mid;
        } else {
            low = mid + 1;
        }
    }
    cout << result << '\n';
}