fzu_noip 1039(盖楼-线段树)

Posted on by
内容目录

盖楼

时限：1s内存：32M

★问题描述:

S举办了一场盖楼比赛，有n位选手参赛，将这n位选手编号为1到n。比赛刚开始时第i位选手的房子的初始高度为Ai，每过一天该选手的房子高度增加Bi。S想知道比赛开始后T天编号为L到R的选手中，造的最高的房子高度为多少。

★数据输入：

输入数据的第一行为两个整数N，Q。(1<=N，Q<=30000)。接下来N行，表示每个选手的初始房子高度和房子每天增长高度，每行两个数Ai,Bi（1<=Ai,Bi<=10^9）。接下来Q行，表示Q个询问，每行3个数Li，Ri，Ti(1<=Li<=Ri<=N,0<=Ti<=1000000)。所有输入都是整数。

★结果输出:

对于每个询问输出一行一个整数,表示比赛开始后Ti天编号为Li到Ri的选手中造的房子的最大高度。

 

输入示例

输出示例

5 4

4 1

3 5

6 2

3 5

6 5

1 5 2

1 3 5

1 1 0

1 5 0

16

28

4

6

5 4

6 1

5 1

2 5

4 3

6 1

2 4 1

3 4 5

1 4 5

1 2 0

7

27

27

6

 

本来是半平面交+线段树合并（归并合并），暴力居然能过


const
   maxn=30000;
var
   n,q,i,j,l,r,p,t:longint;
   a,b:array[1..maxn] of longint;
begin
   read(n,q);
   for i:=1 to n do read(a[i],b[i]);
   for i:=1 to q do
   begin
      read(l,r,t);
      p:=b[l]*t+a[l];
      for j:=l+1 to r do
         if (p<b[j]*t+a[j]) then p:=b[j]*t+a[j];
      writeln(p);
   end;
end.