Submission

Score: 0

User: theem1502

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

Language: cpp

Time: 0.156 second

Submitted On: 2026-02-14 18:18:33

#include <bits/stdc++.h>
using namespace std;
int fenwick[20000003];
    //int newarray[20000000];
        int prefixarray[20000003];
void update(int index, int value) {
    while(index < 20000000) {
        fenwick[index] += value;
        index += index & (-index);
    }

}

int ask(int index) {
    int sum = 0;
    while(index >0) {
        sum += fenwick[index];
        index -= index & (-index);
    }
    return sum;
}

int main() {
    int num;
    cin >> num;
    for (int i = 0; i < num; i++) {
        int first, second;
        cin >> first >> second;
        update(first + 1, 1);
        update(second + 1, -1);

    }
/*
    for (int i = 0; i < 20; i++) {
        cout << ask(i) << " ";
    }
    cout << "\n";
*/
    prefixarray[0] = ask(1);

    for (int i = 1; i <= 20000000; i++) {
        prefixarray[i] = prefixarray[i-1] + ask(i+1);
    }
/*
    for (int i = 0; i < 100; i++) {
        cout << prefixarray[i] << " ";
    }
    */
 //   cout << "\n";

    int cnt = prefixarray[20000000];
  //  cout << "cnt: " << cnt << "\n";
    int median = cnt / 2;
    cout << lower_bound(prefixarray, prefixarray + 20000000, median) - prefixarray;






}