백준25412 Measures

작성일 | In

문제 링크

  • http://icpc.me/25412

문제 출처

  • 2022 CEOI Day2 2번

사용 알고리즘

  • 세그먼트 트리

시간복잡도

  • $O((N+M) \log (N+M))$

풀이

Subtask 1. $N \leq 2\,000, M \leq 10$ (10점)

모든 점들을 정렬합시다. $i$번째 사람과 $j(> i)$번째 사람은 최소한 $(j-i)D$ 이상 떨어져 있어야 합니다. 따라서 두 사람은 최대 $((j-i)D-(P_j-P_i))/2$ 만큼 이동해야 합니다. 그러므로 $((j-i)D-(P_j-P_i))/2$의 최댓값은 정답의 상한입니다.

$t$초 이후에는 두 사람의 거리가 최대 $2t$ 만큼 변할 수 있습니다. 따라서 정답 $T$는 모든 $i < j$에 대해 $P_j-P_i+2T \geq (j-i)D$를 만족해야 합니다. 식을 정리하면 $T \geq ((j-i)D-(P_j-P_i))/2$가 되므로 정답의 하한도 구했습니다.

상한과 하한이 같으므로 단순히 $((j-i)D-(P_j-P_i))/2$의 최댓값을 $O(M(N+M)^2)$ 시간에 구해서 출력하면 됩니다.

Subtask 2. $N \leq 200\,000, M \leq 10$ (24점)

함수 $f(i, j) = (j-i)D-(P_j-P_i)$를 정의합시다. $O(N^2)$개의 쌍을 모두 보지 않고 $f$의 최댓값을 구해야 합니다.
식을 정리하면 $f(i, j) = (jD-P_j) + (P_i-iD)$를 얻을 수 있고, 이때 $i$를 고정하면 $f(i, \ast)$의 최댓값은 suffix maximum을 이용해 구할 수 있습니다. 따라서 $O(N \log N + NM)$에 해결할 수 있습니다.

아래 코드는 매번 std::sort를 호출하기 때문에 $O(NM \log N)$이지만, 새로 들어온 사람만 적절한 위치에 삽입하면 $O(N \log N + NM)$이 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, M, D;
vector<ll> V;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> D; V.resize(N);
    for(auto &i : V) cin >> i;
    for(int iter=1; iter<=M; iter++){
        int t; cin >> t; V.push_back(t);
        sort(V.begin(), V.end());

        ll res = 0, sz = V.size();
        vector<ll> mx(sz);
        for(int i=0; i<sz; i++) mx[i] = i * D - V[i];
        for(int i=sz-2; i>=0; i--) mx[i] = max(mx[i], mx[i+1]);
        for(int i=0; i<sz; i++) res = max(res, mx[i] + V[i] - i * D);
        cout << res/2 << (res % 2 ? ".5" : "") << " \n"[iter==M];
    }
}

Subtask 3. $N = 0, M \leq 200\,000, b_i \leq b_{i+1}$ (59점)

맨 뒤에 새로운 값이 추가되기 때문에 suffix maximum을 전처리할 수 없습니다. 하지만 $j$를 고정한 다음 $f(\ast, j)$의 최댓값을 구하는 방식으로 접근하면 $P_i-iD$의 prefix maximum을 구하는 것이므로 동일한 방법으로 해결할 수 있습니다.
원소를 중간에 삽입하거나 정렬할 필요가 없기 때문에 시간 복잡도는 $O(M)$입니다.

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, M, D;
vector<ll> V;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> D; V.resize(N);
    for(auto &i : V) cin >> i;

    ll res = 0; vector<ll> prefix;
    for(int iter=1; iter<=M; iter++){
        int t; cin >> t;
        if(M <= 10){
            V.push_back(t); sort(V.begin(), V.end());
            ll sz = V.size(); res = 0;
            vector<ll> mx(sz);
            for(int i=0; i<sz; i++) mx[i] = i * D - V[i];
            for(int i=sz-2; i>=0; i--) mx[i] = max(mx[i], mx[i+1]);
            for(int i=0; i<sz; i++) res = max(res, mx[i] + V[i] - i * D);
        }
        else{
            prefix.push_back(t - iter*D);
            if(prefix.size() >= 2) prefix.back() = max(prefix.back(), prefix[prefix.size()-2]);
            res = max(res, iter*D - t + prefix.back());
        }
        cout << res/2 << (res % 2 ? ".5" : "") << " \n"[iter==M];
    }
}

Subtask 4. $N = 0, M \leq 200\,000$ (100점)

새로운 수가 추가되었을 때 함수 $f(i, j) = (j-i)D-(P_j-P_i)$가 어떻게 변화하는지 살펴봅시다.
$f(i, j) = (jD-P_j)+(P_i-iD) = (jD-P_j)-(iD-P_i)$의 최댓값을 구하는 것이 목표입니다. 어떤 위치 $x$에 수를 삽입하면 $x$보다 오른쪽에 있는 원소들의 $iD-P_i$ 값이 $D$씩 증가합니다.
기존에 있던 원소들 간의 $f$ 값은 이미 계산되어 있으므로, 새로 $x$에 삽입한 원소들에 의해 바뀐 $f$값, 즉 ($x$의 오른쪽에서의 최댓값) - ($x$의 왼쪽에서의 최솟값)을 구해서 정답에 반영해야 합니다.

$x$보다 오른쪽에 있는 원소들의 값을 $D$씩 증가시키는 연산, 구간의 최댓값과 최솟값을 찾는 연산은 좌표 압축을 수행한 뒤 세그먼트 트리를 이용해 처리할 수 있습니다.

전체 시간 복잡도는 $O((N+M) \log (N+M))$입니다.

전체 코드

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
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PLL = pair<ll, ll>;
constexpr int SZ = 1 << 18;

PLL T[SZ<<1]; ll L[SZ<<1];
const PLL O(0x3f3f3f3f3f3f3f3f, 0xc0c0c0c0c0c0c0c0);
PLL Merge(const PLL &a, const PLL &b){
    return make_pair(min(a.first,b.first), max(a.second,b.second));
}
void Push(int node, int s, int e){
    T[node].first += L[node];
    T[node].second += L[node];
    if(s != e) L[node<<1] += L[node], L[node<<1|1] += L[node];
    L[node] = 0;
}
void Update(int l, int r, ll v, int node=1, int s=0, int e=SZ-1){
    Push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){ L[node] += v; Push(node, s, e); return; }
    int m = (s + e) / 2;
    Update(l, r, v, node<<1, s, m);
    Update(l, r, v, node<<1|1, m+1, e);
    T[node] = Merge(T[node<<1], T[node<<1|1]);
}
void Set(int x, ll v, int node=1, int s=0, int e=SZ-1){
    Push(node, s, e);
    if(s == e){ T[node] = {v, v}; return; }
    int m = (s + e) / 2;
    if(x <= m) Set(x, v, node<<1, s, m), Push(node<<1|1, m+1, e);
    else Set(x, v, node<<1|1, m+1, e), Push(node<<1, s, m);
    T[node] = Merge(T[node<<1], T[node<<1|1]);
}
PLL Query(int l, int r, int node=1, int s=0, int e=SZ-1){
    Push(node, s, e);
    if(r < s || e < l) return O;
    if(l <= s && e <= r) return T[node];
    int m = (s + e) / 2;
    return Merge(Query(l, r, node<<1, s, m), Query(l, r, node<<1|1, m+1, e));
}

ll N, M, D, P[202020], F[202020];
vector<pair<ll,ll>> C;

void Add(int x){ for(x+=3; x<202020; x+=x&-x) F[x]++; }
int Get(int x){ int ret = 0; for(x+=3; x; x-=x&-x) ret += F[x]; return ret; }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> D; C.reserve(N+M);
    for(int i=1; i<=N+M; i++) cin >> P[i], C.emplace_back(P[i], i);
    sort(C.begin(), C.end());

    ll res = 0;
    fill(T, T+SZ*2, O);
    for(int q=1; q<=N+M; q++){
        int pos = lower_bound(C.begin(), C.end(), make_pair(P[q], (ll)q)) - C.begin();
        int idx = Get(pos); Add(pos);
        Set(pos, idx * D - P[q]);
        Update(pos+1, C.size()-1, D);
        res = max(res, Query(pos, C.size()-1).second - Query(0, pos).first);
        if(q > N) cout << res / 2 << (res % 2 ? ".5" : "") << " \n"[q==N+M];
    }
}