boj 28018 시간이 겹칠까?

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

28018번: 시간이 겹칠까?

특정 시간에 학생이 몇명 채워져 있는지 구하는 문제입니다.

이 문제는 학생들이 머무르는 구간 l ~ r이 주어집니다.

l ~ r 구간을 모두 채워주어야 하며, 매 쿼리의 l ~ r 구간의 누적을 구하면 O(N^2)의 시간이 걸려 TLE가 발생합니다.

매 쿼리마다 누적합을 갱신하지 않고, 시작과 끝에만 표시하여 한꺼번에 누적합을 구할 수 있는 imos 기법을 활용합니다.

 

학생은 l 시간에 들어와서 r 시간까지 머무릅니다.

따라서 학생이 존재하기 시작하는 l 시간에 +1, 학생이 없는 시간인 r + 1 시간에 -1을 누적합니다.

마지막에 누적합을 갱신하면 O(N) 시간 만으로도 문제를 해결할 수 있습니다.

 

 

#include <iostream>
#define MAX 1000001
using namespace std;
 
int dp[MAX];
int N, M;
 
void func() {
    for (int i = 1; i < MAX; i++) {
        dp[i] += dp[i - 1];
    }
 
    int x;
    cin >> M;
    while (M--) {
        cin >> x;
        cout << dp[x] << '\n';
    }
}
 
void input() {
    int l, r;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> l >> r;
        dp[l]++;
        dp[r + 1]--;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}