Gym 100623B Billboard(線段樹)

構造一棵線段樹，記錄每個區間裡的最小長度

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200010;
int minwid[4*N];
int h,w,n;
inline int L(int u)
{
    return u<<1;
}
inline int R(int u)
{
    return (u<<1)+1;
}
inline int P(int u)
{
    return u>>1;
}
void weihu(int u)
{
    while(u)
    {
        int t=min(minwid[L(u)],minwid[R(u)]);
        if(minwid[u]>=t)
            break;
        minwid[u]=t;
        u=P(u);
    }
}
int put(int x)
{
    if(x+minwid[1]>w)
        return -1;
    int u=1,lv=1,rv=h;
    while(lv!=rv)
    {
        if(x+minwid[L(u)]<=w)
        {
            u=L(u);
            rv=(lv+rv)/2;
        }
        else
        {
            u=R(u);
            lv=(lv+rv)/2+1;
        }
    }
    minwid[u]+=x;
    weihu(P(u));
    return lv;
}
int main()
{
    freopen("billboard.in","r",stdin);
    freopen("billboard.out","w",stdout);
    //freopen("i.txt","r",stdin);
    scanf("%d%d%d",&h,&w,&n);
    h=min(h,200000);
    while(n--)
    {
        int x;
        scanf("%d",&x);
        printf("%d\n",put(x));
    }
    return 0;
}