Submission

[PP-SS][SSSSS][SSSSSSSSSS]

Score: 0

User: mydKN

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-15 00:23:35

#include<bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

int n;
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<pii> vec;
stack<int> stk;
int sum;
vector<int> bs;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	for(int i=0;i<n;++i){
		int st, en;
		cin >> st >> en;
		pq.emplace(st, -1);
		pq.emplace(en, 1);
	}
	while(!pq.empty()){
		auto [val, t] = pq.top();
		pq.pop();
		if(t == 1 && stk.size() == 1){
			vec.emplace_back(stk.top(), val);
			stk.pop();
			//cout << "pop\n";
		}
		else if(t == 1 && stk.size() != 1){
			stk.pop();
		}
		else if(t == -1){
			stk.emplace(val);
			//cout << "push\n";
		}
	}
	//for(auto e : vec) cout << e.first << " " << e.second << "\n";
	for(auto e : vec){
		int cnt = e.second - e.first;
		sum += cnt;
		if(!bs.empty()) bs.emplace_back(bs.back() + cnt);
		else bs.emplace_back(cnt);
	}
	sum /= 2;
	int i = 0;
	for(auto e : bs){
		//cout << e << " ";
		if(sum - e <= 0){
			break;
		}
		++i;
		sum -= e;
	}
	//cout << "\n";
	cout << vec[i].first + sum - 1;
}