백준25493 까다로운 형제

작성일 | In

문제 링크

  • http://icpc.me/25493

사용 알고리즘

  • 세그먼트 트리
  • 스위핑
  • DP

시간복잡도

  • $O(N \log^2 N)$

풀이

어떤 점이 어디까지 영향을 미치는지 그림을 그려보면 자연스럽게 스위핑 풀이를 찾을 수 있습니다.

$(x_1, y_1)$에서 $(x_2, y_2)$로 갈 수 있는 조건을 생각해 봅시다.
매번 원점과의 거리가 더 커지도록 이동해야 하므로 $x_2+y_2 > x_1+y_1$을 만족해야 합니다. 또한, 거리가 $K$ 이하인 곳으로만 이동할 수 있으므로 $x_2-y_2-K \leq x_1-y_1 \leq x_2-y_2+K$, $x_2+y_2-K \leq x_1+y_1 \leq x_2+y_2+K$를 만족해야 합니다.
좌표계를 45도 돌려서, 즉 $(x’, y’)$를 $(x+y, x-y)$로 변환해서 생각합시다.

위에서 세운 부등식은 아래 두 개의 부등식으로 정리할 수 있습니다.

  • $x_1 < x_2 \leq x_1+K$
  • $y_1-K \leq y_2 \leq y_1+K$

x축을 기준으로 라인 스위핑을 합니다. $x_i$을 만나면 $[y_i-K, y_i+K]$ 구간에 $D(i)$를 넣고, $x_1+K$를 만나면 구간에서 $D(i)$를 제거하면 됩니다. 이 작업은 각 정점마다 multiset 또는 우선순위 큐 2개를 관리하는 세그먼트 트리를 이용해 range update point query를 수행하면 됩니다.

정리하면, 좌표를 45도 회전한 다음 좌표 압축을 하고, 문제 조건을 식으로 정리해서 얻은 부등식을 이용해 세그먼트 트리로 스위핑을 하면 문제를 해결할 수 있습니다. multiset은 아마 시간 초과를 받을 것이고 수선순위 큐 2개는 AC를 받을 수 있을 것입니다.

전체 코드

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int SZ = 1 << 18;
constexpr ll INF = 0xc0c0c0c0c0c0c0c0;

template<class T=int, class O=less<T>>
struct pq_set {
    priority_queue<T, vector<T>, O> q, del;
    const T& top() const { return q.top(); }
    int size() const { return int(q.size()-del.size()); }
    bool empty() const { return !size(); }
    void insert(const T x) { q.push(x); flush(); }
    void pop() { q.pop(); flush(); }
    void erase(const T x) { del.push(x); flush(); }
    void flush() { while(del.size() && q.top()==del.top()) q.pop(), del.pop(); }
};

struct Point{
    ll x, y, c;
    Point() : Point(0, 0, 0) {}
    Point(ll x, ll y, ll c) : x(x), y(y), c(c) {}
    bool operator < (const Point &t) const { return tie(x,y,c) < tie(t.x,t.y,t.c); }
};

struct Event{
    int l, r, idx;
    Event() = default;
    Event(int l, int r, int idx) : l(l), r(r), idx(idx) {}
};

ll N, K;
Point A[202020];
vector<ll> CX, CY;
pq_set<pair<ll,ll>> T[SZ << 1];
pair<ll,ll> D[202020];
vector<Event> E[202020][2];

void Insert(int l, int r, pair<ll,ll> v){
    l |= SZ; r |= SZ;
    while(l <= r){
        if(l & 1) T[l++].insert(v);
        if(~r & 1) T[r--].insert(v);
        l >>= 1; r >>= 1;
    }
}

void Erase(int l, int r, pair<ll,ll> v){
    l |= SZ; r |= SZ;
    while(l <= r){
        if(l & 1) T[l++].erase(v);
        if(~r & 1) T[r--].erase(v);
        l >>= 1; r >>= 1;
    }
}

pair<ll,ll> Get(int x){
    x |= SZ; pair<ll,ll> res = T[x].top();
    while(x >>= 1) res = max(res, T[x].top());
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K; CX.reserve(N+1); CY.reserve(N+1);
    for(int i=1; i<=N; i++){
        ll x, y, c; cin >> x >> y >> c;
        A[i] = {x+y, x-y, c};
        CX.push_back(x+y);
        CY.push_back(x-y);
    }
    sort(A+1, A+N+1);
    CX.push_back(0); CY.push_back(0);
    sort(CX.begin(), CX.end()); CX.erase(unique(CX.begin(), CX.end()), CX.end());
    sort(CY.begin(), CY.end()); CY.erase(unique(CY.begin(), CY.end()), CY.end());
    for(int i=1; i<SZ*2; i++) T[i].insert(make_pair(INF, INF));
    D[0] = {0, 0};

    for(int i=0; i<=N; i++){
        int st = lower_bound(CX.begin(), CX.end(), A[i].x) - CX.begin();
        int ed = upper_bound(CX.begin(), CX.end(), A[i].x+K) - CX.begin();
        int le = lower_bound(CY.begin(), CY.end(), A[i].y-K) - CY.begin();
        int ri = upper_bound(CY.begin(), CY.end(), A[i].y+K) - CY.begin() - 1;
        E[st][0].emplace_back(le, ri, i);
        E[ed][1].emplace_back(le, ri, i);
    }

    for(int ti=0; ti<202020; ti++){
        for(auto [l,r,idx] : E[ti][1]) Erase(l, r, D[idx]);
        for(auto [l,r,idx] : E[ti][0]){
            auto [sum,cnt] = Get(lower_bound(CY.begin(), CY.end(), A[idx].y) - CY.begin());
            if(idx != 0) D[idx] = { sum + A[idx].c, cnt + 1 };
        }
        for(auto [l,r,idx] : E[ti][0]) Insert(l, r, D[idx]);
    }
    auto res = *max_element(D, D+N+1);
    cout << res.first << " " << res.second;
}