Submission

[P-SSS][SSSSS][SSSSSSSSSS]

Score: 0

User: Pera

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-19 08:49:38

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

int main() {
    ios_base::sync_with_stdio(false);
    
    int n;
    cin >> n;

    vector<pair<int, int>> xy(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        xy[i].first = x;
        // from x to y - 1
        xy[i].second = y;
    }

    int totalbooks{0};
    for (int i = 0; i < n; i++) {
        totalbooks += xy[i].second - xy[i].first;
    }

    int medianindex{floor(totalbooks / 2)};

    int low{0};
    int high{20000000};
    int median_val{-1};

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

        for (int i = 0; i < n; i++) {
            int x = xy[i].first;
            int y = xy[i].second;
            if (mid >= y) {
                count_less_mid += (y - x);
            } else if (mid >= x) {
                count_less_mid += (mid - x + 1);
            }
        }

        if (count_less_mid >= medianindex + 1) {
            median_val = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << median_val - 1 << '\n';
    
}