Submission

[PPPPP][PPPPP][PPPPPPPPPP]

Score: 100

User: fluke

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-14 21:37:02

#include <bits/stdc++.h>
#define ll long long 
#define f first 
#define s second 
#define pii pair<int,int>
#define piii tuple <int,int,int> 
#define emb emplace_back
#define em emplace 
#define all(x) x.begin(),x.end()
#define sp <<" "<<
#define DB cout<<"\n";system("pause");
using namespace std;

ll inf = 2e18;
int mod = 1e9+7;

int di[] = {0,1,0,-1};
int dj[] = {1,0,-1,0};

bool cmp(pii &a , pii &b){
    if(a.f != b.f)return a.f < b.f;
    return a.s > b.s;
}


int main(){
//ios::sync_with_stdio(false);cin.tie(0);
    int n;
    cin>>n;

    vector <pii> line;
    int sum = 0;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        line.emb(x,1);
        line.emb(y,-1);
        sum += y-x;
    }

    sort(all(line),cmp);

    int book = 0 ;
    int size = 0;
    int before = 0;
    int now = 0;
    int index_mean = (sum)/2;
    if(index_mean == 0)index_mean = 1; 

    for(int i=0;i<n*2;i++){
        now = line[i].f;
        book += size * (now - before);
        // cout<<book;
        // DB
        
        if(book >= index_mean){

            if(book == index_mean){
                cout<<now -1 ;
                return 0;
            }
                    
            // while(book_now >= index_mean){
            //     book_now -= size;
            //     num_now -- ;
            // }

            int diff = book - index_mean;
            cout<<now - 1 - diff/size;
            return 0;
        }

        before = now;
        size += line[i].s;

    }

}