题目链接:https://vjudge.net/problem/HDU-2795

思路:h = 1e9行不通,因为广告是1*w的,所以n个广告最多只需要 h = n的高度,那么h=2e5就可以接受了。

用树状数组维护区间最大值。

从前往后区间查询哪一大块块首先满足条件,然后一直缩小区间,直到区间长度等于1,输出答案,然后修改该点可用的w,

再修改区间最大值。

 #include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <stack>
#include <vector>
#include <list>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second const int N = 2e5+;
int a[N],c[N];
int n,h,w; inline int lb(int x){
return x&(-x);
} void update(int inx){
for(int i = inx; i <= h; i += lb(i)){
c[i] = a[i];
int d = lb(i);
if(d == ) continue;
for(int j = ; j < d; j <<= )
c[i] = max(c[i], c[i-j]);
}
} inline bool fun(int& l,int& r,int it){
while(r <= h){
// cout << "fun" << endl;
if(c[r] < it){
l = r;
r += lb(r);
if(r > h) r = l+;//要遍历所有的分块区间
}
else return ;
}
return ;
} void solve(){
while(~scanf("%d%d%d",&h,&w,&n)){
h = h >= n ? n : h;
for(int i = ; i <= h; ++i) a[i] = c[i] = w;//初始化
int it;
for(int p = ; p <= n; ++p){
scanf("%d",&it);
int l = ,r = ,ok = ;
while(fun(l,r,it)){//找是否有满足的区间
// cout << "main" << endl;
ok = ;
if(l == r){
printf("%d\n",l);
a[l] -= it;
update(l);
break;
}
else r = ++l;//缩小区间
}
if(!ok) printf("-1\n");
}
}
} int main(){ // ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
solve(); return ;
}

最新文章

  1. iOS - GeoCoder 地理编码
  2. WinAPI——SetWindowsHookEx设置钩子说明
  3. Stream类
  4. 【Nutch2.2.1基础教程之2.2】集成Nutch/Hbase/Solr构建搜索引擎之二:内容分析
  5. Jquery Validate 动态添加校验
  6. prop()、attr()和data()
  7. Jerry的碎碎念:SAPUI5, Angular, React和Vue
  8. 如何开发由Create-React-App 引导的应用(三)
  9. 【django之form和认证系统小练习】
  10. 排序算法Java实现(冒泡排序)
  11. BBS论坛(十九)
  12. Spark源码剖析 - SparkContext的初始化(一)
  13. Django组件 之 ookie 和 session
  14. 【CFD之道】2018年原创文章汇总
  15. POJ - 3984 迷宫问题 dfs解法
  16. 天融信资料下载官方FTP服务器
  17. (android高仿系列)今日头条 --新闻阅读器 (二)
  18. SharpGL学习笔记(六) 裁剪变换
  19. Object之总结(一)
  20. tomcat运行springboot项目war包

热门文章

  1. js-dom运动我有废话要说
  2. Word目录生成
  3. mabatis中的元素属性
  4. JMeter之BeanShell断言---equals使用
  5. Network Saboteur (DFS)
  6. 玩转UITableView
  7. Git的安装与TortoiseGit的安装和汉化
  8. Docker 运行容器 CentOS7 使用systemctl 启动报错 Failed to get D-Bus connection: Operation not permitted
  9. 《数据结构与算法》—— O(3N)=O(N) ?
  10. Ubuntu18.04LTS安装docker报错:Command &#39;lsb_release&#39; not found