题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2795

题意:w*h的公告板要贴公告,公告是w*1的,每个公告有先后顺序,要使每个公告贴的位置尽可能地高,问每个公告最高贴多高。不能贴就输出-1。特别“不”需要注意的是,题目给的n数据范围很大,但是n只有200000。所以说可以不用关心h的范围。

线段树叶子节点维护公告板行的剩余宽度,尽可能地往左子树走。更新在查询的时候完成,不要忘记向上更新线段树。

 #include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; #define fr first
#define sc second
#define pb(a) push_back(a)
#define Rint(a) scanf("%d", &a)
#define Rll(a) scanf("%I64d", &a)
#define Rs(a) scanf("%s", a)
#define Fread() freopen("in", "r", stdin)
#define Fwrite() freopen("out", "w", stdout)
#define Rep(i, n) for(int i = 0; i < (n); i++)
#define For(i, a, n) for(int i = (a); i < (n); i++)
#define Cls(a) memset((a), 0, sizeof(a))
#define Full(a) memset((a), 0w7f7f, sizeof(a)) #define lrt rt << 1
#define rrt rt << 1 | 1
const int mawn = ;
int sum[mawn<<];
int w, h, n, t; void pushUP(int rt) {
sum[rt] = max(sum[lrt], sum[rrt]);
} void build(int l, int r, int rt) {
sum[rt] = w;
if(l == r) return;
int m = (l + r) >> ;
build(l, m ,lrt);
build(m+, r, rrt);
// pushUP(rt);
} void update(int p, int w, int l, int r, int rt) {
if(l == r) {
sum[rt] -= w;
return;
}
int m = (l + r) >> ;
if(p <= m) update(p, w, l, m, lrt);
else update(p, w, m+, r, rrt);
pushUP(rt);
} int query(int l, int r, int rt, int w) {
if(l == r) {
sum[rt] -= w;
// update(l, w, 1, n, 1);
return l;
}
int m = (l + r) >> ;
int ret = sum[rt<<] >= w ? query(l, m, lrt, w) : query(m+, r, rrt, w);
pushUP(rt);
return ret;
} int main() {
// Fread();
while(~scanf("%d%d%d", &h, &w, &n)) {
h = min(h, n);
build(, h, );
while(n--) {
Rint(t);
if(sum[] < t) printf("-1\n");
else printf("%d\n", query(, h, , t));
}
}
return ;
}

最新文章

  1. 支付宝PC即时到账和手机网站支付同步
  2. auto_clipboard
  3. 结对实验报告-android计算器设计
  4. 重构第15天 移除重复的代码(Remove Duplication)
  5. 【新产品发布】【EVC8001 磁耦隔离式 USB 转 RS-485】
  6. UIStackView入门
  7. Redis系列-存储篇hash主要操作函数小结
  8. 网页爬虫--scrapy入门
  9. mysql describe
  10. ZOJ 3603 Draw Something Cheat
  11. scheme corotuine
  12. log4net使用特定的解释
  13. Splunk 丰富数据方法
  14. mysql 开发进阶篇系列 1 SQL优化(show status命令)
  15. ABAP 文件选择框
  16. 实现mypwd&amp;mybash&amp;myod&amp;读者写者
  17. Python爬取网易云歌单
  18. linux df查看硬盘使用量 du查看文件所占大小
  19. 三: vue组件开发及自动化工具vue-cli
  20. python-mongodb基本操作都在这了

热门文章

  1. 使用Redis做MyBatis的二级缓存
  2. ACCESS数据库C#操作类(包含事务)
  3. Reference in the manifest does not match the identity of the downloaded assembly
  4. diahosting的低配vps弱爆了
  5. sed 详解
  6. 【POJ】【3537】Crosses and Crosses
  7. 【UVA】【10828】随机程序
  8. auto_ptr的设计动机
  9. prim求MST
  10. 玩转图片Base64编码