Submission

[PP-SS][SSSSS][SSSSSSSSSS]

Score: 0

User: Pera

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-24 21:15:13

#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, lib.second) - lib.first + 1;
        }
    }
    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;
        y--;
        books += y - x + 1;
        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;
           // result = mid;
        } else {
            low = mid + 1;
        }
    }
    cout << low << '\n';
}