首页 > 代码库 > 【HDU2795】Billboard

【HDU2795】Billboard

2024-08-15 06:24:27   221人阅读

本质上，区间最大值；

高为区间长度，宽度为每个元素初始大小

PS：1 <= h,w <= 10^9，而n次放置都是放在可能位置的最上面

     所以对于每一种case，取h和n的最小值建树

技术分享
 1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 const int N=200010; 5 int n,h,w,len[N<<2]; 6 int max(int,int),query(int,int,int,int),min(int,int); 7 void update(int),build(int,int,int); 8 int main(){     9     int d,pos;10     while (~scanf("%d %d %d",&h,&w,&n)){11         h=min(h,n);12         build(1,h,1);13         for (int i=1;i<=n;i++){14             scanf("%d",&d);15             if (d>len[1]) printf("-1\n");16             else printf("%d\n",query(1,1,h,d));17         }18     }19     return 0;20 }21 void build(int l,int r,int i){22     len[i]=w;23     if (l==r) return;24     int mid=(l+r)>>1;25     build(l,mid,i<<1);26     build(mid+1,r,i<<1|1);27 }28 int query(int i,int l,int r,int d){29     if (l==r){30         len[i]-=d;return l;31     }32     int mid=(l+r)>>1,ans;33     if (len[i<<1]>=d) ans=query(i<<1,l,mid,d);34     else ans=query(i<<1|1,mid+1,r,d);35     update(i);36     return ans;37 }38 void update(int i){39     len[i]=max(len[i<<1],len[i<<1|1]);40 }41 int max(int x,int y){42     return x>y?x:y;43 }44 int min(int x,int y){45     return x<y?x:y;46 }
STD

 

【HDU2795】Billboard


联系
我们