D. Billboard
D. Billboard
On September 1, the billboard was empty. One by one, the announcements started being put on the billboard.
Each announcement is a stripe of paper of unit height. More specifically, the i-th announcement is a rectangle of size 1 * wi.
When someone puts a new announcement on the billboard, she would always choose the topmost possible position for the announcement. Among all possible topmost positions she would always choose the leftmost one.
If there is no valid location for a new announcement, it is not put on the billboard (that's why some programming contests have no participants from this university).
Given the sizes of the billboard and the announcements, your task is to find the numbers of rows in which the announcements are placed.
Input
The first line of the input file contains three integer numbers, h, w, and n (1 <= h,w <= 10^9; 1 <= n <= 200,000) - the dimensions of the billboard and the number of announcements.
Each of the next n lines contains an integer number wi (1 <= wi <= 10^9) - the width of i-th announcement.
Output
Sample Input
3 5 5
2
4
3
3
3
Sample Output
1
2
1
3
-1 解题:线段树线段树线段树。。。。。。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
const int maxn = ;
struct node {
int lt,rt,lmax,rmax;
} tree[maxn<<];
int h,w,n,ans;
void build(int lt,int rt,int v) {
tree[v].lt = lt;
tree[v].rt = rt;
if(lt == rt) {
tree[v].lmax = tree[v].rmax = w;
return;
}
int mid = (lt+rt)>>;
build(lt,mid,v<<);
build(mid+,rt,v<<|);
tree[v].lmax = max(tree[v<<].lmax,tree[v<<].rmax);
tree[v].rmax = max(tree[v<<|].lmax,tree[v<<|].rmax);
}
void add(int val,int v) {
if(val > max(tree[v].lmax,tree[v].rmax)) {
ans = -;
return;
}
if(tree[v].lt == tree[v].rt) {
if(tree[v].lmax >= val) {
ans = tree[v].lt;
tree[v].lmax -= val;
tree[v].rmax -= val;
} else ans = -;
return;
}
if(val <= tree[v].lmax) add(val,v<<);
else add(val,v<<|);
tree[v].lmax = max(tree[v<<].lmax,tree[v<<].rmax);
tree[v].rmax = max(tree[v<<|].lmax,tree[v<<|].rmax);
}
int main() {
int temp;
while(~scanf("%d %d %d",&h,&w,&n)) {
if(h > n) h = n;
build(,h,);
while(n--) {
scanf("%d",&temp);
ans = -;
add(temp,);
printf("%d\n",ans);
}
}
return ;
}
最新文章
- CSS字体记录
- RDIFramework.NET ━ .NET快速信息化系统开发框架 V3.0 版新增系统参数管理
- 数论学习笔记之解线性方程 a*x + b*y = gcd(a,b)
- 原创:goldengate从11.2升级到12.1.2
- IE7 -- 鼠标移入显示下拉框 不显示的问题 / 以及宽度问题
- A4纸网页打印——宽高设置
- 虚拟化之xenserver
- linux中Apache更Nginx环境配置教程
- 译文:javascript function中的this
- (转载)有关反演和gcd
- Android开发视频学习(1)
- Android监测手指上下左右滑动屏幕
- java.util.concurrent.ExecutionException: org.apache.catalina.LifecycleException: Failed to start component [StandardEngine[Catalina].StandardHost[localhost].StandardContext
- java框架之SpringBoot(10)-启动流程及自定义starter
- 让docker容器开机启动
- linux文件管理之查找
- 银行卡号码校验算法(Luhn算法,又叫模10算法)
- shell快捷方式总结
- ABAP-ALV详解
- c++11多线程学习笔记之二 mutex使用