Submission

[PP-SS][SSSSS][SSSSSSSSSS]

Score: 0

User: Cmoss9

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

Language: cpp

Time: 0.003 second

Submitted On: 2025-03-18 22:12:15

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

int main() {
    int n; 
    cin >> n;

    vector<pair<int, int>> ranges(n);
    int max_val = 0; 
    int total_books = 0; 
   
    for (int i = 0; i < n; i++) {
        cin >> ranges[i].first >> ranges[i].second;
        total_books += (ranges[i].second - ranges[i].first); 
        max_val = max(max_val, ranges[i].second); 
    }
    vector<int> freq(max_val + 1, 0);

    for (int i = 0; i < n; i++) {
        for (int j = ranges[i].first; j < ranges[i].second; j++) {
            freq[j]++;
        }
    }

    int half = total_books / 2;
    int accumulated = 0;
    int median = -1;
    // cout << total_books << '\n';
    if (total_books % 2 == 0) {
        int first_middle = -1, second_middle = -1;
        for (int i = 0; i <= max_val; i++) {
            accumulated += freq[i];
            if (accumulated >= half && first_middle == -1) {
                first_middle = i;
            }
            if (accumulated > half) {
                second_middle = i;
                break;
            }
        }
        //cout << first_middle << ' ' << second_middle << '\n';
        median = (first_middle + second_middle) / 2;
    } 
    else {
        for (int i = 0; i <= max_val; i++) {
            accumulated += freq[i];
            if (accumulated >= half) {
                median = i;
                break;
            }
        }
    }
    cout << median << endl;
}