Submission

----------

Score: 0

User: Cmoss9

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-18 21:49:21

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

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int room;
    cin >> room;
    int x[room], y[room];
    

    for (int i = 0; i < room; i++) {
        cin >> x[i] >> y[i];
    }

    int max_value = 0;
    for (int i = 0; i < room; i++) {
        max_value = max(max_value, y[i]);
    }
    // cout << max_value << '\n';

    vector<int> freq(max_value + 1, 0);

    for (int i = 0; i < room; i++) {
        for (int j = x[i]; j < y[i]; j++) {
            freq[j]++;
        }
    }

    int total = 0;
    int median = -1;
    int half = 0;
    
    // First pass to find the half size
    for (int i = 0; i <= max_value; i++) {
        total += freq[i];
    }

    half = total / 2; // half population

    // Second pass to find the median value
    total = 0;
    for (int i = 0; i <= max_value; i++) {
        total += freq[i];
        if (total >= half) {
            median = i;
            break;
        }
    }

    cout << median << endl;

    return 0;
}