Submission

[PP-SS][SSSSS][SSSSSSSSSS]

Score: 0

User: dwad2

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-21 00:08:55

#include <bits/stdc++.h>

using namespace std;

pair<int, int> check(vector<pair<int, int>> &list, int x) {

    int sumleft = 0, sumright = 0;

    for(int i = 0; i < list.size(); i++) {
        if(list[i].first < x) {
            if(list[i].second <= x) sumleft += (list[i].second - list[i].first);
            else sumleft += (x - list[i].first);
        }
    }

    for(int i = 0; i < list.size(); i++) {
        if(list[i].second > x) {
            if(list[i].first > x) sumright += (list[i].second - list[i].first);
            else sumright += (list[i].second - x - 1);
        }
    }

    return {sumleft, sumright};
}

int search(vector<pair<int, int>> &list, int left, int right, int maxsum) {

    int mid = (left + right) / 2;
    //cout << mid << endl;

    if(left == mid) {
        if(check(list, right).first > (maxsum / 2) - 1) return mid;
        else return right; 
    }

    else if(check(list, mid).first < (maxsum / 2) - 1) return search(list, mid, right, maxsum);
    else return search(list, left, mid, maxsum);

}

int main() {

    cin.tie(0)->sync_with_stdio(0);

    int n;
    cin >> n;

    int s, e;
    long long maxsum = 0;
    vector<pair<int, int>> list(n);
    for(int i = 0; i < n; i++) {
        cin >> s >> e;
        maxsum += (e - s);
        list[i] = {s, e};
    }

    cout << search(list, 0, 2e7, maxsum);

    return 0;
}