BOJ 18407(가로 블록 쌓기)풀이

solved.ac 티어 : 플래 3

www.acmicpc.net/problem/18407

18407번: 가로 블록 쌓기

새로 떨어지는 블록은 자신의 구간에서의 최댓값+1이다. 그러므로 세그레이지로 max를 구해주고 max+1 값을 구간에 저장해준다. 그리고 max값이 최대 높이일 경우 최대 높이를 올려준다음 마지막에 나온 최대 높이를 출력해주면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct qu{
    ll left,right;
};
vector<qu>l(2000001);
ll a,tree_size;
vector<ll>tree(8010000);
vector<ll>tree1(8010000);
vector<ll>A;
ll seg(ll n,ll s,ll e){
    if(s==e){return tree[n]=0;}
    return tree[n]=max(seg(n*2,s,(s+e)/2),seg(n*2+1,(s+e)/2+1,e));
}
void propagate(ll n,ll s,ll e){
    if(tree1[n]!=0){
        if(s!=e){
            tree1[n*2]=max(tree1[n*2],tree1[n]);
            tree1[n*2+1]=max(tree1[n*2+1],tree1[n]);
        }
        tree[n]=max(tree[n],tree1[n]);
        tree1[n]=0;
    }
}
ll max1(ll n,ll s,ll e,ll left,ll right){
    propagate(n,s,e);
    if(left>e||right<s){return 0;}
    if(left<=s&&e<=right){return tree[n];}
    return max(max1(n*2,s,(s+e)/2,left,right),max1(n*2+1,(s+e)/2+1,e,left,right));
}
void change(ll n,ll s,ll e,ll s1,ll e1,ll f){
    propagate(n,s,e);
    if(s1<=s&&e<=e1){tree1[n]=max(f,tree1[n]);propagate(n,s,e);return;}
    if(e1<s||s1>e){return;}
    change(n*2,s,(s+e)/2,s1,e1,f);
    change(n*2+1,(s+e)/2+1,e,s1,e1,f);
    tree[n]=max(tree[n*2],tree[n*2+1]);
}
int main()
{
    ll b,c,d,q,k,gh,gk,cnt=0,val=0,as=0;
    scanf("%lld",&a);
    int i;
    for(i=0;i<a;i++){
        scanf("%lld %lld\n",&l[i].left,&l[i].right);
        as=l[i].right;
        l[i].right+=l[i].left-1;
        l[i].left=as;
        
        A.push_back(l[i].left);
        A.push_back(l[i].right);
    }
    sort(A.begin(),A.end());
    A.erase(unique(A.begin(),A.end()),A.end());
    for(i=0;i<a;i++){
        l[i].left=lower_bound(A.begin(),A.end(),l[i].left)-A.begin();
        l[i].right=lower_bound(A.begin(),A.end(),l[i].right)-A.begin();
    }
    seg(1,0,2000000);
    for(i=0;i<a;i++){
        //printf("%lld %lld\n",l[i].left,l[i].right);
        val=max1(1,0,2000000,l[i].left,l[i].right);
        if(val==cnt)cnt++;
        //printf("#%lld\n",val);
        change(1,0,2000000,l[i].left,l[i].right,val+1);
        //printf("%lld\n",cnt);
    }
    printf("%lld\n",cnt);
}