Submission

Score: 0

User: Jibhong

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-22 18:47:59

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair<int, bool> pib;
vector<pib> mem;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    int md = 0;

    for (int i = 0; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        md += v - u;
        mem.emplace_back(u, 1);
        mem.emplace_back(v, 0);
    }

    md /= 2;

    sort(mem.begin(), mem.end(), [](const pib &a, const pib &b) {
        return a.F == b.F ? a.S > b.S : a.F < b.F;
    });

    int last = 0;
    int now = 0;
    int cnt = 0;
    int idx = 0;
    int foundIdx = -1;
    bool iFoundIt = false;

    for (int i = 0; i < mem.size(); ++i) {
        auto e = mem[i];

        if (last == e.F) {
            cnt += e.S ? 1 : -1;
            continue;
        }

        idx += cnt * (e.F - last);

        if (idx >= md) {
            foundIdx = i;
            iFoundIt = true;
            break;
        }

        last = e.F;
        cnt += e.S ? 1 : -1;
    }

    if (!iFoundIt || foundIdx == -1 || foundIdx >= mem.size()) {
        cout << "Error: No valid index found\n";
        return 1;
    }

    if (cnt == 0) {
        cout << mem[foundIdx].F - 1;
    } else {
        cout << mem[foundIdx].F - (idx - md) / cnt - 1;
    }

    return 0;
}