백준 20440 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 혼내주기

 

좌표 압축 문제를 연습하려고 태그된 문제를 풀었는데, 우큐 풀이밖에 안 떠올라서 우큐로 풀었다. 가장 빠른 구간을 출력한다는 점 외에는 11000 강의실 배정 문제와 다를 게 없다.
누적 합 + 좌표 압축 태그인데, 아무리 생각해봐도 떠오르지가 않고 그렇게 푼 풀이들은 너무 난해해서 이해할 수가 없다... 실행 시간이 우큐가 빨라서 그냥 이렇게 푸는게 맞는 것 같다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

pair<int, int> arr[1000000];
int n;

void input() {
    fastio;
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> arr[i].first >> arr[i].second;
    }
}

int main() {
    input();
    sort(arr, arr+n);

    priority_queue<int> pq;
    int from, to, ans = 0;
    for(int i = 0; i < n; ++i){
        pq.push(-arr[i].second);

        int prev = -1;
        while(arr[i].first >= -pq.top()) {
            prev = -pq.top();
            pq.pop();
        }

        if(pq.size() > ans) {
            from = arr[i].first;
            to = -pq.top();
            ans = pq.size();
        } else if(pq.size() == ans && prev == arr[i].first) {
            to = -pq.top();
        }
    }
    cout << ans << "\n";
    cout << from << " " << to;
}