백준 20440 - 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 (C++)

문제

• 문제 링크

  
   BOJ 20440 - 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 
  

• 문제 요약

$N$개의 모기 출입 정보가 주어진다.
이때, 모기가 가장 많이 있는 시간대의 모기 마릿수와 그 연속 구간을 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ N ≤ 1,000,000$

$0 ≤ T_E < T_X ≤ 2,100,000,000$

알고리즘 분류

• 누적 합(prefix_sum)
• 정렬(sorting)
• 값 / 좌표 압축(coordinate_compression)

풀이

   수직선 상에 $N$번의 업데이트 후 최종 상태 출력.. 전형적인 imos법의 형태이다.

그러나 주어지는 좌표 범위가 $N$에 비해 난감하다.
어차피 존재할 수 있는 좌표 상태는 많아봐야 $2,000,000$가지일테니, 좌표 압축을 써먹어주면 되겠다.

한가지 주의할 점이 있다. 단순하게 std::map으로 좌표 압축을 하면 상수 차이로 TLE를 얻어 맞을 수 있다.
맞다. 내가 그랬다.

그러니 C++의 국룰 좌표 압축 방식인 sorting 후 erase + unique 조합을 써먹어주자.

전체 코드

#include<bits/stdc++.h>
#define N 1000001
using namespace std;
 
struct { int p, q; } a[N];
vector <int> V;
int n, i, s[N << 1];
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (cin >> n; i < n; i++)
    {
        cin >> a[i].p >> a[i].q;
        V.push_back(a[i].p), V.push_back(a[i].q);
    }
    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());
    for (i = 0; i < n; i++)
    {
        s[lower_bound(V.begin(), V.end(), a[i].p) - V.begin() + 1]++;
        s[lower_bound(V.begin(), V.end(), a[i].q) - V.begin() + 1]--;
    }
    int r{}, x{}, y{};
    for (i = 1; i < (N << 1); r = max(r, s[i++]))
        s[i] += s[i - 1];
    for (i = 0; i < (N << 1); i++)
        if (s[i] == r)
            (x = x ? x : i), (y = y ? y + 1 : x);
        else if (x && s[i] ^ r)
            break;
    cout << r << '\n' << V[x - 1] << ' ' << V[y];
}

comment

끝