注意h的范围和n的范围,纵向建立线段树
题意:h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子
思路:每次找到最大值的位子,然后减去L
线段树功能:query:区间求最大值的位子(直接把update的操作在query里做了)
3 5 5
2
4
3
3
3
1
2
1
3
-1
2015-05-15
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
const int INF=0x3f3f3f3f;
const double eps=1e-;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root 1,n,1
#define mid ((l+r)>>1)
const int MAXN=;
int n,m,t;
int num[MAXN],w,h;
struct Node
{
int l,r;
int sum;
}node[MAXN<<];
void build(int l,int r,int rt)
{
node[rt].l=l;
node[rt].r=r;
node[rt].sum=w;
if(l==r) return;
build(lson);
build(rson);
}
int query(int val,int rt)
{
if(node[rt].l==node[rt].r)
{
node[rt].sum-=val;
return node[rt].l;
}
int ret=;
if(node[rt<<].sum>=val) ret=query(val,rt<<);
else ret=query(val,rt<<|);
node[rt].sum=max(node[rt<<|].sum,node[rt<<].sum);
return ret;
}
int main()
{
int i,j,k,tt;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
while(~scanf("%d%d%d",&h,&w,&n))
{
if(h>n) h=n;
int a;
build(,h,);
for(i=;i<=n;i++)
{
scanf("%d",&a);
if(node[].sum<a) printf("-1\n");
else printf("%d\n",query(a,));
}
}
}
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int maxn=;
int sum[maxn<<];
int n,m,t,h,w;
void pushup(int rt)
{
sum[rt]=max(sum[rt<<],sum[rt<<|]);
}
void build(int l,int r,int rt)
{
sum[rt]=w;
if(l==r) return;
int m=(l+r)>>;
build(lson);
build(rson);
}
int query(int add,int l,int r,int rt)
{
if(l==r)
{
sum[rt]-=add;
return l;
}
int m=(l+r)>>;
int ret;
if(sum[rt<<]>=add)
{
ret=query(add,lson);
}
else ret=query(add,rson);
pushup(rt);
return ret;
}
int main()
{
int i,j,k;
//freopen("1.in","r",stdin);
while(scanf("%d%d%d",&h,&w,&n)!=EOF)
{
if(h>n) h=n;
build(,h,);
for(i=;i<=n;i++)
{
scanf("%d",&k);
if(sum[]<k) printf("-1\n");
else printf("%d\n",query(k,,h,));
}
}
return ;
}