선 긋기

Problem link: https://www.acmicpc.net/problem/2170

sweeping 문제인데, 하필 직전에 화성지도를 푼 나머지 자칫하면 segment tree를 쓸 뻔했다.

안 써도 각 정점의 opening / closing을 함께 저장하고, sweeping을 진행하면서 open된 횟수가 양수인 지점들에서 직선의 길이를 더해주면 쉽게 풀 수 있다.

#include <iostream>
#include <algorithm>
#include <cstdint>
#include <vector>

using namespace std;

int main(void)
{
  // For faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  size_t N;
  cin >> N;

  vector<pair<int, int> > POINTS;

  for (size_t it = 0; it < N; ++it)
  {
    int X, Y;
    cin >> X >> Y;
    POINTS.emplace_back(X, 1);
    POINTS.emplace_back(Y, 0);
  }

  sort(POINTS.begin(), POINTS.end());

  int64_t sum = 0;

  int prev = POINTS[0].first;
  size_t opened_points = 0;
  for (const auto& point : POINTS)
  {
    if (opened_points > 0)
    {
      sum += point.first - prev;
    }

    if (point.second == 1)
    {
      ++opened_points;
    }
    else
    {
      --opened_points;
    }

    prev = point.first;
  }

  cout << sum << "\n";

  return 0;
}