20985 - Snowball

작성일 | In

20985 - Snowball

무한한 1차원 길 위 초기 크기 $0$인 $N(1\leq N\leq 2\times10^5)$개의 눈덩이가 각각 위치 $L_1, L_2\dots,L_N$에 있습니다. 초기의 길 위에는 눈이 쌓여있고, 눈덩이가 거리 1을 눈 위에서 구르면 크기가 1 증가하고, 눈덩이가 지나간 길 위의 눈은 사라집니다. 모든 눈덩이가 동시에 $Q(1\leq Q\leq 2\times10^5)$개의 명령을 받아 좌/우로 움직일 때, 최종적인 눈덩이들의 크기를 구하는 것이 문제입니다.

다음과 같은 관찰을 할 수 있습니다.

관찰 1. $i$번째 눈덩이 가 밟을 수 있는 눈은 $i-1$번째와 $i+1$번째 눈덩이의 초기 위치 사이 뿐입니다. 그 밖의 눈은 다른 눈덩이가 밟게 됩니다.
관찰 2. $i$번째 눈덩이와 $i+1$번째 눈덩이의 상호작용을 관찰해 봅시다. $k$번째 쿼리를 처리한 뒤 눈덩이가 초기 기준 왼쪽으로 최대한 간 거리를 $left_k$, 오른쪽으로 최대한 간 거리를 $right_k$이라 했을 때 $left_k+right_k$가 $L_{i+1}-L_i$보다 작다면 두 눈덩이는 만나지 않고, 각각 $right_k$, $left_k$만큼의 눈을 확보할 수 있습니다. 그러다 $left_k+right_k$가 $L_{i+1}-L_i$를 넘어가는 순간 두 눈덩이의 경로가 겹치게 되고, 더 이상 두 눈덩이 사이에 눈은 남지 않습니다. 이 때 마지막 눈을 가져가는 눈덩이는 넘어가는 순간의 명령 방향으로 결정되게 됩니다.

쿼리마다 구간의 크기가 어떻게 변하는지 배열에 저장해 놓고, 원소의 크기가 $L_{i+1} - L_i$보다 커지는 시점을 이분탐색으로 찾아줄 수 있습니다. 이렇게 각 눈덩이마다 왼쪽/오른쪽으로 얼마나 많은 눈을 획득하는지 총 $O(N\log N)$에 계산할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q; cin >> n >> q;
    vector<ll> a;
    a.push_back(-LLINF);
    for(int i=1; i<=n; i++) {
        ll x; cin >> x; a.push_back(x);
    }
    a.push_back(LLINF);
    vector<pair<ll, ll>> b;
    vector<ll> c;
    vector<ll> d;
    ll cur = 0;
    ll mx = 0, mn = 0;
    b.push_back({0, 0});
    c.push_back(0);
    d.push_back(0);
    for(int i=0; i<q; i++) {
        ll x; cin >> x;
        cur += x;
        mx = max(mx, cur);
        mn = min(mn, cur);
        b.push_back({mn, mx});
        c.push_back(abs(mn) + abs(mx));
        d.push_back(x);
    }
    for(int i=1; i<=n; i++) {
        ll Ldis = a[i] - a[i-1];
        ll Lans = 0;
        int id = upper_bound(all(c), Ldis) - c.begin();
        if(id == sz(c)) {
            Lans = -b.back().ff;
        } else {
            Lans += -b[id-1].ff;
            if(d[id] < 0) {
                Lans += Ldis - c[id-1];
            }
        }
        ll Rdis = a[i+1] - a[i];
        ll Rans = 0;
        id = upper_bound(all(c), Rdis) - c.begin();
        if(id == sz(c)) {
            Rans = b.back().ss;
        } else {
            Rans += b[id-1].ss;
            if(d[id] > 0) {
                Rans += Rdis - c[id-1];
            }
        }
        cout << Lans + Rans << '\n';
    }
}