[백준] 10167: 금광

0. 문제 주소

 

https://www.acmicpc.net/problem/10167

10167번: 금광

 

 

1. 풀이

 

 

 1. 좌표의 범위때문에 좌표 압축을 해주어야 한다.

 

지금까지는 좌표 압축을 너무 원시적으로 했는데, 좋은 테크닉을 찾아서 주워왔다.

 

x좌표, y좌표를 각각 따로 xco, yco 벡터에 저장해둔 뒤, 정렬 후 중복되는 원소들을 제거해 준다.

 

다음 원래 좌표를 순회하며, 이번 x좌표와 y좌표가 각각 xco, yco에서 몇 번째에 있는지 lower_bound로 찾아주고 대체한다.

 

2. 직사각형의 네 변을 항상 점을 포함하게 잡아도 된다.

 

3. y좌표 기준 오름차순으로 먼저 정렬하고, 같은 점들은 x좌표 기준 오름차순으로 정렬한다.

 

4. 모든 y좌표 y1에 대해 다음과 같은 작업을 수행한다.

 

4-0. y1이 증가할 때마다 x좌표를 index로 갖는 "최대 연속 부분 수열 합 세그먼트 트리"를 초기화한다.

 

4-1. y1 < y2를 만족시키는 모든 y2를 작은 것부터 큰 순서대로 잡는다.

 

4-2. y2가 증가할 때마다 해당 y좌표를 갖는 모든 점들을 세그먼트 트리에 update 한다.

 

4-3. 한 수평선에 있는 점들의 update가 끝났으면 현재 전체 구간에서의 "최대 연속 부분 수열 합"의 값을 현재까지의 최댓값과 비교하여 갱신한다.

 

 

 

자세한 그림 및 설명은 https://blog.naver.com/kks227/220605936611를 참고하면 된다.

[10167번] 금광

 

내가 코드를 쓰면서 실수했던 부분은 다음과 같다.

 

 

1. update를 해줄 때 leaf 노드에 val 값을 대입 연산자를 써서 대입해 버렸는데, 이 경우  y좌표가 올라가면서 동일한 x좌표를 갖는 점을 다시 만날 때 문제가 생긴다. 따라서 기존에 있는 값에 val 값을 더해주어야 한다.

 

2. 한 y좌표 별로 점들이 가지는 w값을 트리에 업데이트 시킬 때, leaf 노드에만 값을 넣어두고 한 줄이 끝날 때 모든 점을 갱신시키는 함수를 호출했는데, 이 경우 불필요한 연산이 포함되어 TLE가 난다. 따라서 매번 새로운 점을 만나면 root 노드까지 update를 바로 해주고, 최대값 비교만 한 줄이 끝날 때 처리해주면 된다.

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>

#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

struct point{
    ll x, y, w;
    bool operator < (const point &A){
        if (y == A.y) return x < A.x;
        return y < A.y;
    }
}; 

struct Node{
    ll sum, l, r, m;
    
    ll Max(){
        return max(max(sum, l), max(r, m));
    }
};

Node tree[8300];
int N;
int leaf_size;
vector<point> P;
vector<ll> xco;
vector<ll> yco;


void clear(){
    for (int i=0;i<8300;i++){
        tree[i].sum = tree[i].l = tree[i].r = tree[i].m = 0;
    }
}

Node updatenode(Node &A, Node &B){
    Node ret;
    ret.sum = A.sum + B.sum;
    ret.l = max(A.sum + B.l, max(A.l, A.sum));
    ret.r = max(B.sum + A.r, max(B.r, B.sum));
    ret.m = max(A.r + B.l, max(A.m, B.m));
    return ret;    
}

void update(int ind, ll val){
    ind += leaf_size;
    tree[ind].l = tree[ind].r = tree[ind].m = tree[ind].sum += val;
    while(ind > 1){
        ind /= 2;
        tree[ind] = updatenode(tree[ind*2], tree[ind*2+1]);
    }
}

ll getind(vector<ll> &vt, ll val){
    return lower_bound(all(vt), val) - vt.begin();
}


int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d", &N);
    leaf_size = 1 << ((int)ceil(log2(N));

    ll x, y, w;
    for (int i=0;i<N;i++){
        scanf("%lld %lld %lld", &x, &y, &w);
        P.push_back({x, y, w});
        xco.push_back(x);
        yco.push_back(y);
    }
    
    // grid compression 
    sort(all(xco));
    sort(all(yco));
    xco.erase(unique(all(xco)), xco.end());
    yco.erase(unique(all(yco)), yco.end());
    for (int i=0;i<N;i++){
        P[i].x = getind(xco, P[i].x);
        P[i].y = getind(yco, P[i].y);
    }
    
    sort(all(P));

    
    int yrange = P.back().y;
    
    int s = 0; // y1 
    int i = 0; // y2
    ll ret = 0;
    while(s <= yrange){
        i = 0;
        clear();
        while(i < N){
            if (P[i].y < s) { // find y2
                i++;
                continue;
            }
            update(P[i].x, P[i].w);
            if (i+1 == N || P[i].y != P[i+1].y){
                ret = max(ret, tree[1].Max());
            }
            i++;
        }
        s++;
    }
    
    printf("%lld\n", ret);
    
    return 0;
}