【work】

【问题描述】

假设现在离noip还有m天,有n个人要去参赛。

他们每个人都有一个预定的训练量r[i],所以每一天他们都抓紧时间练习。

但是由于条件限制,第i天只有t[i]的时间可以练习。

我们都知道,一个人在开始干活以前总要浪费一些时间做一些杂七杂八的事情。

现在我们假定第i个人每天在训练前浪费时间是固定的,记为d[i]。

这段浪费掉的时间过后,选手会专心致志训练,他们会充分利用剩下的时间。

然而一个可能的情况时,一个人还在无所事事的时候,某一天的训练时间已经过去了,所以他那一天什么事情都没有做。

现在请问每个人在第几天的时候可以完成自己的训练人数。当然会存在志向远大但是很懒惰的人到最后也是做不完的情况。

【输入格式】

第一行两个整数n,m,表示人数和天数;

接下来一行m个整数t[i];

接下来n行每行两个整数d[i],r[i]

【输出格式】

一行输出n个整数表示每个人在第几天可以完成自己的工作,如果完不成,输出0;

【输入样例】

3 3

4 2 5

1 3

2 5

3 4

【输出样例】

1 3 0

【数据范围】

对100%的输入数据:1≤n,m≤200000,1≤t[i]≤1000000,0≤d[i]≤1000000,1≤r[i]≤1000000

这道题可以用线段树解决。

首先可以看出对一个人,有用的天数一定是t[j]>d[i]的,所以我们可以将t和d都降序排列,以天数作为区间建线段树。

对于一个人,将t比他大的天数扔进线段树里,记录一下线段树每个节点的和是由几天组成的,查询和即可。

时间复杂度O(nlogn)

下面是代码:

 

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*