[ABC128 E] Roadwork

난이도: 1840

 

태그

• Offline Query (오프라인 쿼리)
  쿼리 자체의 순서를 바꾸지는 않지만, 쿼리를 모두 받은 뒤 처리하기 때문에 넣었다.
  그와는 별개로, 개인적으로 이 문제에서 \( Q \)보다 \( N \)이 훨씬 쿼리 같다고 느끼기도 했고.
• Binary Search (이진 탐색)
• Disjoint-Set Union
  • Skipping the checked cells using DSU (DSU로 이미 사용한 칸 건너뛰기)
    요약하자면, 인접한 사용된 칸들을 DSU로 묶어서, 한 번에 점프뛰는 그런 느낌이다.
    /<14595> 동방 프로젝트 (Large)를 생각해보자.

 

풀이

1. 공사에 대해 생각해보기

\( [S, T) \) 시간에 위치 \( X \)에서 일어나는 공사는, 어떤 출발시각 \( D \)에 영향을 미칠까요?

 

모든 사람은 \( 1 \)의 속도로 이동하므로, \( [S-X, T-X) \) 시각에 출발하는 사람들에게 영향을 끼치게 됩니다.

 

2. 이동하는 사람에 대해 생각해보기

\( D \)초에 출발하는 사람에게 영향을 주는 공사들을 모아봅시다.

모든 공사가 주는 영향은 위치 \( X \)에서 멈추게 하는 것이므로, 출발한 사람은 처음으로 만난 \( X \)에서 멈추게 됩니다.

 

즉, \( \min X \)에서 멈추게 되겠죠.

 

3. 이를 토대로, 사람들에게 공사 결과를 빠르게 적용시켜보기

\( X \)가 작은 공사부터 확인해봅시다.

이렇게 하면, 아직까지 영향을 받지 않는 사람들에 대해서만 계산해주면 됩니다.

 

쿼리는 \( D \)의 오름차순으로 정렬되어있으므로, 어떤 공사가 영향을 주게 되는 사람들의 인덱스는 \( [s, e) \)의 구간으로 나타낼 수 있습니다.

이 구간의 답을 \( X \)로 갱신한 뒤, 구간을 하나로 묶으면서 아직 갱신되지 않은 위치를 가리키도록 DSU를 갱신해주면 됩니다.

 

\( X \)가 큰 것부터 보면서, Range Set Query를 날리는 풀이도 있다.

큰 것부터 보면 항상 새로운 값으로 덮어씌울 수 있기 때문이다.

 

코드

pi3 arr[200020];
 
int qrr[200020]; int par[200020];
int ans[200020];
 
int fnd(int v){ return par[v] = (par[v]==v ? v : fnd(par[v])); }
void uni(int v, int w){ par[fnd(v)] = fnd(w); }
 
void Main(){
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++){ cin >> arr[i].fr.fr >> arr[i].fr.sc >> arr[i].sc; }
    for (int i = 1; i <= q; i++){ cin >> qrr[i]; }
    sort(arr+1, arr+n+1, [](pi3 p1, pi3 p2){ return p1.sc < p2.sc; });
    memset(ans, -1, sizeof(ans));
    for (int i = 1; i <= n; i++){
        ll st = arr[i].fr.fr, ed = arr[i].fr.sc;
        ll x = arr[i].sc; st -= x; ed -= x;
        int p = lower_bound(qrr+1, qrr+q+1, st) - qrr;
        //cout << "BIN " << i << ' ' << p << endl;
        while (p <= q){
            if (qrr[p] >= ed){ break; }
            if (ans[p] != -1){ p = fnd(p)+1; }
            else{
                ans[p] = x; par[p] = p;
                if (1 <= p-1 && ans[p-1] != -1){ uni(p-1, p); }
                if (p+1 <= q && ans[p+1] != -1){ uni(p, p+1); }
                p += 1;
            }
        }
    }
    for (int i = 1; i <= q; i++){ cout << ans[i] << endl; }
}