题目名称 1266. [NOIP2012] 借教室
输入输出 classrooms.in/out
难度等级 ★★★
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 20 简单对比
题目来源 2012-11-11
开放分组 全部用户
提交状态
分类标签
通过:344, 提交:2000, 通过率:17.2%
GravatarTA 100 0.227 s C++
GravatarBennettz 100 0.304 s C++
GravatarTA 100 0.381 s C++
GravatarSt.Burning\ 100 0.392 s C++
Gravatar_Itachi 100 0.481 s C++
Gravatarnew ioer 100 0.483 s C++
Gravatar_IOSTREAM_ 100 0.714 s C++
GravatarRapiz 100 0.849 s C++
Gravatar_Itachi 100 0.858 s C++
Gravatarconfoo 100 0.863 s C++
关于 借教室 的讨论
数据范围打错了
Gravatar馒头
2012-11-17 15:52 1楼
线段数比赛的时候还是写错了一点,导致值得了40分
错误如下
向上返回的时候取左右子树的最小值,去最小值的时候没有加上传递量。
GravatarQhelDIV
2012-11-26 11:08 2楼
不说什么了,
熬夜会影响智商。。。。
GravatarQhelDIV
2012-12-07 07:38 3楼
似乎就是二分?
GravatarHobo
2013-08-15 13:51 4楼
晕,用的是O(n+m)的算法,却不如O(nlgm)的快。
GravatarQWERTIer
2013-10-24 22:11 5楼
m打成n,居然过了18个点。
Gravatarranto
2013-11-19 17:58 6楼
回复 @ranto :
ORZ人品帝
Gravatarcstdio
2013-11-20 13:19 7楼
神犇们,看看我的代码拿错了,答案错误啊。。。。。。
GravatarRP++
2014-08-30 11:04 8楼
GravatarJSX
2014-09-10 08:57 9楼
先用线段树水到85,丧心病狂地用读入优化+静态化搞到90……最后才知道差分序列有这种用法QAQ……果然自己太弱
借自己的楼临时贴一下90分的区间修改+区间查询的线段树…… @chs
GravatarAsm.Def
2014-11-07 18:11 10楼
回复 @cstdio @ranto : ORZ大萌帝和人品帝
GravatarAsm.Def
2014-09-17 20:05 11楼
Gravatar传奇
2014-10-26 16:37 12楼
Gravatar传奇
2014-10-29 19:02 13楼
STO5楼!!O(n+m)!!
GravatarTA
2014-11-04 15:34 14楼
迷之TEL....把数组多开了个0竟然就不T了.....而且SCANF竟然比CIN多30分...QAQ然后读入优化没有什么卵用QAQ
Gravatar四季木哥
2015-08-21 08:41 15楼
论线段树的常数影响……
Gravatardevil
2015-10-14 09:58 16楼
低空飞过最后一个点
Gravatarmikumikumi
2015-08-25 11:15 17楼
实在是太慢了。。。。。。差分序列和求和序列,有时间再打个线段树
GravatarSatoshi
2015-09-18 17:50 18楼
Gravatarstdafx.h
2015-10-08 13:52 19楼
Gravatarstdafx.h
2015-10-08 13:51 20楼
评测机有问题?本地不到0.1秒的点交上来全TTTTTTTT,什么情况?
Gravatarlenibomb
2015-10-08 15:15 21楼
让代码出来晒晒太阳
Gravatarforever
2015-10-08 15:42 22楼
第一次成功打模板,纪念一下……
Gravatar啊吧啦吧啦吧
2015-10-13 19:43 23楼
二分答案+暴力扫描AC一发。还是规规矩矩学正解吧= =
Gravatarthomount
2015-10-28 21:01 24楼
Pascal 的inc(a,b)和 dec(a,b) 比 a:=a+b;和a:=a-b; 快得多.得多.得多.得多.
GravatarConanQZ
2016-01-20 17:54 25楼
Gravatar粘粘自喜
2016-07-05 14:00 26楼
线段树+打表水之。
测试点防打表,只检查N和M就wa得更多
GravatarNewBee
2016-07-08 14:56 27楼
回复 @New_Bee丶 :
节操何在...
GravatarHzoi_
2016-07-08 14:57 28楼
GravatarAntiLeaf
2017-05-25 15:58 29楼
GravatarAntiLeaf
2017-05-25 15:58 30楼
为什么线段树的mid不能是全局变量TAT把mid放进去就对了
Gravatar槿柒
2016-08-13 17:09 31楼
总算get了差分数组2333
Gravatar安呐一条小咸鱼。
2016-08-13 17:56 32楼
第一发差分数组
Gravatar牧殇
2016-08-13 18:00 33楼
没加读入优化最后一个点 T 了
下输入文件的时候发现超过10M ......果断关了
Gravatar残星誓言
2016-09-22 19:01 34楼
有没有像我一样的SB写splay?
GravatarFoolMike
2016-09-28 16:26 35楼
线段树常数大如狗,最后一个点低空飞过……
GravatarMarvolo
2016-09-28 16:26 36楼
尝试使用暴力法优化线段树失败......
GravatarAntiLeaf
2016-10-06 15:33 37楼
线段树卡常失败,,,
GravatarTabing010102
2016-10-30 10:19 38楼
据说线段树结点中存指针与位运算求下标相比效果拔群(在某些题目中似乎能卡过树状数组)
Gravatarrvalue
2017-03-07 21:35 39楼
差分真好玩
GravatarJustWB
2017-07-22 23:44 40楼
线段树
GravatarHyoi_Turkey
2017-09-02 22:00 41楼
二分答案bug多成狗。。果然蒟蒻。。积分500+留念。。
Gravatar_WA自动机
2017-09-06 18:06 42楼
线段树lazy没设为0WA了一次。。。对不起党和人民
Gravatarxzz_666
2017-09-12 09:24 43楼
人傻自带大常数qwq,话说我线段树没有优化居然一遍95
没有认真审题的蒟蒻以为先输入的是区间后输入的是值结果被卡半天
Gravatar芒硝
2017-10-11 15:55 44楼
线段树写跪
GravatarShirry
2017-10-20 08:20 45楼
还是太垃圾了啊我
GravatarHyoi_Turkey
2017-10-20 21:09 46楼
用二分即可,该问题具有单调性——答案之前的肯定都能借到。
因此,二分判断某一天及其以前的每一天借教室的总数是否小于当天可用教室数即可。
判断时求借教室总数可用差分求前缀和。
Gravatar小字、小瓶子
2017-10-31 09:17 47楼
线段树好慢
GravatarHzoi_QTY
2017-10-31 19:44 48楼
滚去学了学差分。。
GravatarHzoi_QTY
2017-10-31 20:27 49楼
二分写错,五颜六色
GravatarAPWTMECRD
2017-11-02 12:29 50楼
为什么我的快读gg了
GravatarHale
2018-10-27 19:48 51楼

1266. [NOIP2012] 借教室

★★★   输入文件:classrooms.in   输出文件:classrooms.out   简单对比
时间限制:1 s   内存限制:128 MB

【题目描述】

在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要 向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。 

面对海量租借教室的信息,我们自然希望编程解决这个问题。 

我们需要处理接下来n天的借教室信息,其中第i天学校有ri个教室可供租借。共有m份 订单,每份订单用三个正整数描述,分别为dj,sj,tj,表示某租借者需要从第sj天到第tj天租 借教室(包括第sj天和第tj天),每天需要租借dj个教室。 

我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提 供dj个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。 

借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教 室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申 请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。 

现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改 订单。

【输入格式】

第一行包含两个正整数n,m,表示天数和订单的数量。 

第二行包含n个正整数,其中第i个数为ri,表示第i天可用于租借的教室数量。 

接下来有m行,每行包含三个正整数dj,sj,tj,表示租借的数量,租借开始、结束分别在 第几天。 

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。

【输出格式】

如果所有订单均可满足,则输出只有一行,包含一个整数 0。否则(订单无法完全满足) 输出两行,第一行输出一个负整数-1,第二行输出需要修改订单的申请人编号。

【样例输入】

4 3 
2 5 4 3 
2 1 3 
3 2 4 
4 2 4 

【样例输出】

-1
2

【输入输出样例说明】

第 1 份订单满足后,4 天剩余的教室数分别为 0,3,2,3。第 2 份订单要求第 2 天到 第 4 天每天提供 3 个教室,而第 3 天剩余的教室数为 2,因此无法满足。分配停止,通知第 2 个申请人修改订单。

【数据范围】

对于 10%的数据,有1 ≤ n,m ≤ 10; 

对于 30%的数据,有1 ≤ n,m ≤ 1000; 

对于 70%的数据,有1 ≤ n,m ≤ 10^5; 

对于 100%的数据,有1 ≤ n,m ≤ 10^6,0 ≤ ri,dj ≤ 10^9,1 ≤ sj ≤ tj ≤ n。