POJ-3277: City Horizon

keyword

座標圧縮　segment tree　C++

問題概要

a,b(0

解法

座標圧縮してsegment treeに突っ込む。区間に対する更新処理と点に対する最大値が求められればよい。segment treeの部分は蟻本を参考にして書いた。segment treeの配列のサイズを勘違いして通すのに時間がかかった。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX_N = 40009;
typedef long long int64;

vector<int> nums;
int dat[8*MAX_N];
int fs[MAX_N], ts[MAX_N], hs[MAX_N];
int N, M, RMQ_N;

int pack(int n){
    return distance(nums.begin(), lower_bound(nums.begin(), nums.end(), n));
}

void init(){
    for(int i=0; i<N; i++){
        nums.push_back(fs[i]);
        nums.push_back(ts[i]);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    M = nums.size();
    RMQ_N = 1;
    while(RMQ_N < M) RMQ_N *= 2;
}

int64 query(int k){
    k += RMQ_N - 1;
    int ret = dat[k];
    while(k > 0){
        k = (k-1)/2;
        ret = max(ret, dat[k]);
    }
    return (int64)ret;
}

void update(int a, int b, int h, int k, int l, int r){
    if(r <= a || b <= l) return ;
    if(a <= l && r <= b){
        dat[k] = max(dat[k], h);
    }
    else{
        update(a,b,h,k*2+1,l,(l+r)/2);
        update(a,b,h,k*2+2,(l+r)/2,r);
    }
}

void update(int from, int to, int h){
    update(from, to, h, 0, 0, RMQ_N);
}

int64 solve(){
    init();

    for(int i=0; i<N; i++){
        update(pack(fs[i]), pack(ts[i]), hs[i]);
    }

    int64 ans = 0;
    for(int i=0; i<M-1; i++){
        ans += (nums[i+1] - nums[i])*query(i);
    }
    return ans;
}

int main(){
    scanf("%d",&N);
    for(int i=0; i<N; i++) scanf("%d%d%d",fs+i,ts+i,hs+i);
    printf("%lld\n",solve());
    return 0;
}