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

https://www.acmicpc.net/problem/20440

 

선분 imos법을 통해 모기들의 증감을 관리하여 밀도가 가장 높으면서 긴 구간을 출력하면 된다.

 

다만 imos법을 사용하면 한 곳에서 여러마리의 모기가 들어왔다 나갈 수 있으므로 가장 긴 구간을 구하기 위해 각 지점에서 발생하는 모기의 출입을 하나의 pair로 합쳐줘야 한다.

 

본인은 unordered_map을 사용하여 이를 간단히 처리했다.

 

그 후 다음 과정을 거친다.

 

1. 모기의 출입을 정리한 후 구간을 스위핑 하면서 현재 저장한 최댓값보다 더 높은 값을 찾았을 때 start를 해당 구간의 시작점, end를 -1로 초기화 한다.

 

2. 이전까지 모기의 밀도가 최대고 현재 지점의 밀도가 최댓값보다 작아졌을 때 end가 -1이라면 end를 현재 지점으로 설정하여 구간을 결정해준다.

 

3. 최대값에서 작아진게 아니라면 무시하고 스위핑을 계속한다.

 

위 과정을 반복하면서 얻은 결과가 정답이 된다.

 

관련 구현은 첨부한 소스 코드를 참조한다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;
using ll = long long;
using pii = pair<int, int>;

vector<pii> v;
int n;

void solve()
{
  cin >> n;

  unordered_map<int, int> mp;

  for (int i = 0; i < n; ++i)
  {
    int a, b;
    cin >> a >> b;
    if (mp.count(a)) ++mp[a];
    else mp[a] = 1;
    if (mp.count(b)) --mp[b];
    else mp[b] = -1;
  }

  v.assign(mp.begin(), mp.end());
  sort(v.begin(), v.end());

  int ans = 0, cur = 0;
  int stt = 0, end = -1;

  for (int i = 0; i < v.size(); ++i)
  {
    cur += v[i].second;
    if (cur > ans)
    {
      ans = cur;
      stt = v[i].first, end = -1;
    }
    else if (cur < ans)
    {
      if (end == -1) end = v[i].first;
    }
  }

  cout << ans << '\n' << stt << ' ' << end;
}

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  solve();
}