Submission

Score: 20

User: iij

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

Language: cpp

Time: 0.248 second

Submitted On: 2025-10-20 21:49:12

#include <bits/stdc++.h>

using namespace std;

int qS(vector<int> v, int i) {
    if (v.size() == 1) {
        return v[0];
    }

    int pivot = v[int(v.size()/2)];
    vector<int> lows, highs, pivots;
    for (auto el : v) {
        if (el == pivot) pivots.emplace_back(el);
        if (el < pivot) lows.emplace_back(el);
        if (el > pivot) highs.emplace_back(el);
    }

    if (i < lows.size()) {
        return qS(lows, i);
    } else if (i < lows.size() + pivots.size()) {
        return pivots[0];
    } else {
        return qS(highs, i-lows.size()-pivots.size());
    }
}

int main() {
    int n, x, y;
    cin >> n;
    vector<int> v;
    while(n--) {
        cin >> x >> y;
        for (int i = x; i < y; i++) {
            v.emplace_back(i);
        }
    }
    cout << qS(v, v.size()/2-1);
}