백준 28018 - 시간이 겹칠까? (C++)

문제

• 문제 링크

  
   BOJ 28018 - 시간이 겹칠까? 
  

• 문제 요약

학생 $N$명의 $S_i, E_i$가 주어진다.
$Q$개의 쿼리에 대해 선택할 수 없는 좌석 수를 구해보자.

• 제한

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




$1 ≤ N, Q ≤ 10^5$

$1 ≤ S_i, E_i ≤ 10^6$

알고리즘 분류

• 누적 합(prefix_sum)

풀이

이제 어느정도 웰노운 테크닉이 돼버린, $imos$법 기본 문제이다.

무지성 $Lazy$ $Propagation$을 박아도 되겠지만
업데이트 쿼리가 앞 쪽에 몰려 있고 출력 쿼리가 나중에서야 나온다면, 이제부터 $imos$법 사용 가능성을 고려해보자.

여기선 $1$차원이지만 $2$차원에서의 사용을 연습해보고 싶다면 이 문제 를,
트리와 곁들여보고 싶다면 이 문제 를 풀어 보자.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int n, i, j, p[1000001];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (cin >> n; n--;) cin >> i >> j, p[i]++, p[j + 1]--;
    for (i = 1; i < 1000001; i++) p[i] += p[i - 1];
    for (cin >> n; n--;) cin >> i, cout << p[i] << '\n';
}

comment

끝