[13334] 철로

13334번: 철로

많은 블로그들에서는 Priority Queue를 사용하는 해설을 적어 놓았고 사실 Priority Queue를 쓰는 게 낫긴 한데, 여기서는 Priority Queue를 안 쓰는 방식을 소개한다.

문제의 철로 L의 오른쪽 끝과 수직선 상에 존재하는 가장 왼쪽의 건물이 처음 만날 때부터 왼쪽 끝이 가장 오른쪽의 건물을 지날 때까지 이동한다고 생각하자. 이 상황을 L이 움직임에 따라 각 건물이 L에 추가되었다가 제거되는 것으로 해석할 수 있다.

철로의 오른쪽 끝은 만나는 모든 건물을 L 안에 추가한다.
철로의 왼쪽 끝은 만나는 모든 건물을 L 밖으로 제거한다.

이렇게 L에 건물을 추가하고 제거하는 행동을 해야 하는 '이벤트'를 생각하자. 어떠한 이벤트가 발생할 때 철로의 시작 위치를 이벤트 발생 지점이라고 하면, 각 건물의 위치 $p_b$에 따른 이벤트 발생 지점 $p_e$는 다음과 같다.

건물 추가 : $p_e = p_b - d$
건물 제거 : $p_e = p_b$

 

이 문제에서 고려하여야 할 사항은 지정된 한 쌍의 건물이 모두 L 안에 포함되는 경우를 세어야 한다는 것이고, 이는 이벤트에 특정한 tag를 달아 추가 이벤트가 발생할 때에 arr[tag] += 1, 제거 이벤트가 발생할 떄에 arr[tag] -= 1을 해 준다면 arr[tag]가 2일 경우 카운트하는 방식으로 해결할 수 있다.

 

또 삭제 이벤트의 경우 이벤트가 발생된 해당 건물이 즉시 삭제되는 것이 아니라 그 다음 이벤트가 발생하기 직전에 삭제되어야 하고, 같은 위치에서 여러 이벤트가 발생된 경우 동시에 처리되어야 한다.

struct event {
    int loc;
    int tag;
    bool add;
};

vector<pair<int, int>> tmpp;
vector<event> events;

int c[100001];

int main() {
    fastio;
    
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) {
    	int b1, b2;
        cin >> b1, b2;
        tmpp.push_back({b1, b2});
    }
    int d;
    cin >> d;
    for(int i = 0; i < N; i++) {
        int b1 = tmpp[i].first;
        int b2 = tmpp[i].second;
        events.push_back({ b1 - d, i, true });
        events.push_back({ b1, i, false });

        events.push_back({ b2 - d, i, true });
        events.push_back({ b2, i, false });
    }

    sort(events.begin(), events.end(), [](event& a, event& b) {
        return a.loc < b.loc;
        });

    int i = 0;
    int cnt = 0;
    int mcnt = -1;
    while (i < events.size()) {
        int j = i;
        int loc = events[i].loc;
        while (j < events.size() && events[j].loc == loc) {
            if (events[j].add)
                if (++c[events[j].tag] == 2) cnt++;
            j++;
        }
        if (mcnt < cnt) mcnt = cnt;
        while (i < j) {
            if (!events[i].add)
                if (c[events[i].tag]-- == 2) cnt--;
            i++;
        }
    }

    cout << mcnt;
    return 0;
}​