[BOJ 20985] Snowball

Link

문제 링크

Problem

The JOI plain is a wide plain spreading from west to east. We can consider the JOI plain as a number line. A spot on the JOI plain is denoted by a coordinate. The positive direction of the number line corresponds to the east direction. Now winter comes in the JOI plain. There are N snowballs on it, numbered from 1 to N from the west to the east. In the beginning, the coordinate of the snowball i (1 ≤ i ≤ N) is an integer Xi.

Strong wind blows in the JOI plain in winter. You have observation data of wind for Q days. On the j-th day (1 ≤ j ≤ Q), the wind is described by an integer Wj. If Wj is negative, then the wind blows to the west direction. If Wj is not negative, then the wind blows to the east direction. The strength of the wind is |Wj|.

When wind blows, a snowball is moved to the same direction as the wind, and its length of move is equal to the strength of the wind. In other words, if there is a snowball in the coordinate x in the beginning of the j-th day (1 ≤ j ≤ Q), then the snowball is moved from the coordinate x to the coordinate x + Wj. At the end of the j-th day, the coordinate of the snowball becomes x + Wj. Note that, in each day, the snowballs are moved at the same time, and their speeds are the same.

Initially, the JOI plain is covered with snow. If a snowball is moved on an interval covered with snow, then the snowball accumulates the snow, the weight of the snowball is increased, and the snow on the interval disappears. In other words, for an integer a, assume that the interval from $a$ to $a+1$ is covered with snow. If a snowball is moved on this interval, then the weight of the snowball is increased by 1, and the snow on the interval from a to $a+1$ disappears. However, if a snowball is moved on an interval without snow, the weight of the snowball remains the same.

Initially, the weight of every snowball is 0. It did not snow on the Q days of observation data.

You want to know the weight of each snowball at the end of the Q-th day.

Write a program which, given the initial position of each snowball and observation data of wind for Q days, calculates the weight of each snowball at the end of the Q-th day

Input

Read the following data from the standard input. Given values are all integers.

• $1\leq N \leq 200000$
• $1\leq Q \leq 200000$
• $|X_i|\leq 10^{12}$ $(1\leq i \leq N)$
• $X_i < X_{i+1}$ $(1\leq i \leq N-1)$
• $|W_j|\leq 10^{12}$ $(1\leq j \leq Q)$

N Q
X₁ · · · XN
W₁
.
.
.
WQ

Subtask

Index Score Restriction

1	33	N ≤ 2 000, Q ≤ 2 000.
2	67	No additional constraints.

Subtask 1($\mathcal{O}(NQ)$)

문제의 예제를 직접 손으로 돌려보고, 몇 가지 생각을 해보면 관찰을 몇가지 할 수 있다.

Observation 1

Claim) $i$번째의 시작 좌표를 $p[i]$라 하자. 이때, $i$번째 눈덩이는 $p[i-1]\leq C \leq p[i+1]$에서만 weight를 쌓을 수 있다.

Proof) 만약 $p[i]$에서 $K>p[i+1]$의 weight를 획득하고자 하면, 오른쪽으로 $K-p[i]$만큼 가야 한다.

이때, 모든 눈덩이들이 바람이 불 때마다 움직이므로 $p[i+1]+K-p[i]>K$이고, 따라서 $i+1$번째 눈덩이가 이미 $K$를 지나가게 된다.

따라서 $p[i]$가 이미 $K$에 도달했을 때에는 눈이 없는 상황이 된다.

$p[i]$과 $p[i+1]$ 사이의 구간을 $T[i]$라 하고, $T[0]=-inf$, $T[n]=inf$라 하자.

이때, $T[i]$에서 $i$번째 눈덩이가 오른쪽으로 얼마큼 움직였냐와 $i+1$번째 눈덩이가 왼쪽으로 얼만큼 움직였냐에 따라 눈이 남아있는 양이 달라지게 된다.

Observation 2

바람에 의해서 오른쪽으로 움직인 정도를 $r$, 왼쪽으로 움직인 정도를 $l$이라 하자.

만약, $l+r<T[i]$이면 서로 겹치는 부분 없이 $i$번째 눈덩이는 $l$, $i+1$번째 눈덩이는 $r$만큼 weight를 쌓게 된다.

만일 바람 $V$에 의해 $l+r<T[i]$에서 $l'+V\geq T[i]$로 이동했다고 하면, $i$번째 눈덩이는 $T[i]$에서 $r$만큼, $i+1$번째 눈덩이는 $T[i]-r$만큼 weight를 얻게 된다.

Observation 2에 의해 총 $N$개의 구간 $T[i]$에 대해 매 바람이 불어올 때, $l$과 $r$을 갱신해주면서 구간을 넘어가는지, 만일 넘어갔으면 어느 눈덩이가 얼마큼 가중치를 가져가야 하는지 계산을 해주면서 진행하면 된다.

한 번의 바람 당 $N$개의 구간을 봐야 하므로 복잡도는 $\mathcal{O}(NQ)$

Subtask 2($\mathcal O(Q+NlgN)$)

일단, $l$과 $r$는 매 바람이 불어올 때마다 왼쪽(혹은 오른쪽)으로 눈덩이가 굴러갈 수 있는 정도를 의미하기 때문에, 단조 증가한다.

따라서 $l+r$도 동일하게 단조 증가한다.

이를 이용하면, 몇몇 구간에 대해서는 볼 필요가 없음을 알 수 있는데,

1. 이미 구간의 길이가 $l+r$보다 작아서 이후의 바람이 불어오는 것과 관련 없이 구간 내의 weight가 $0$인 경우
2. 바람이 불어도 $l+r<T[i]$여서 단순히 더해주기만 하는 경우

즉, 우리가 문제에서 특수하게 다루어야 할 부분은 바람 $V$에 의해 $l+r<T[i]~\rightarrow~l'+r'>T[i]$인 부분인 것이고, 이만 아니면 따로 처리를 해줄 필요가 없다.

구간이 짧을수록 weight가 빠르게 사라지므로 구간의 길이를 기준으로 정렬해준 이후에, 매 바람이 불 때마다 구간의 길이와 $l+r$을 비교, 만일 넘었으면 weight를 갱신해주는 식으로 진행한다.

마지막에 구간이 너무 길어서 아무리 바람이 불어도 겹치지 않을 수 있으니, $l+r<T[i]$인 모든 $i$에 대해 $i$번째 눈덩이에는 $r$만큼, $i+1$번째 눈덩이에는 $l$만큼 weight를 더해주면 된다.

정렬을 하는데 $\mathcal{O}(NlgN)$의 시간이 들고, 쿼리를 모두 다 보면서 구간을 한 번씩 다 보므로 $\mathcal{O}(N+Q)$

따라서 총 시간 복잡도는 $\mathcal{O}(Q+NlgN)$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
#define MAX 2000000000005
#define x first
#define y second
 
int p;
ll l, r, v;
vector<pli> co;
ll a[200006], ans[200006];
 
int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    a[0] = -MAX, a[n+1] = MAX;
    for(int i = 1; i<=n;i++) scanf("%lld", &a[i]), co.push_back({a[i+1]-a[i], i}); // range
    sort(co.begin(), co.end());
    while(q--) {
        ll t;
        scanf("%lld", &t);
        if(t>=0) {
            // if t > 0, wind is east direction
            // That means, snowball goes to right, so update right value
            // If |now wind value| > |before wind value|, update. else, not update => max operation
            v += t;
            r = max(r, v);
            // if l + r > (range) + wind east, so Left snowball will be moved
            // Right snowball's weight: L, Left snowball's weight: (range)-L
            // After that, doesn't remain weight => skip
            while(p<=n && co[p].x <= l+r) {
                ans[co[p].y+1] += l;
                ans[co[p].y] += co[p].x - l;
                ++p;
            }
        }
        else {
            // if t < 0, wind is west direction
            // That means, snowball goes to left, so update left value
            // If |now wind value| > |before wind value|, update. else, not update => max operation
            v += t;
            l = max(l, -v);
            while(p<=n && co[p].x <= l+r) {
                ans[co[p].y] += r;
                ans[co[p].y+1] += co[p].x - r;
                ++p;
            }
        }
    }
    for(int i=1;i<=n;i++) printf("%d\n", co[p].y);
    while(p<=n) {
        ans[co[p].y] += r;
        ans[co[p].y + 1] += l;
        ++p;
    }
    for(int i=1; i<=n;i++) printf("%lld\n", ans[i]);
    return 0;
}