Discussion @ 1491. Unreal Story @ Timus Online Judge

Time Limit on test 17 (Pascal)

Posted by Assassin 14 Sep 2007 18:06

Help please!
I don't understand how I can make my program faster.
This algorithm is slow ( n*(b-a) times).

{Time Limit on test 17}
var a,b,c,j:word; q:array[1..100000] of longint; i,n:longint;
begin
readln(n);
for i:=1 to n+1 do begin
readln(a,b,c);
for j:=a to b do q[j]:=q[j]+c;
end;
write(q[1]); for i:=2 to n do write(' ',q[i]);
end.

Edited by author 14.09.2007 18:07

Re: Time Limit on test 17 (Pascal)

Posted by Vedernikoff Sergey 15 Sep 2007 04:23

You should use such structure, as RSQ...

Re: Time Limit on test 17 (Pascal)

Posted by Tolstobrov Anatoliy[Ivanovo SPU] 15 Sep 2007 07:34

O(N) possible

Re: Time Limit on test 17 (Pascal)

Posted by Howl of Despair 6 Feb 2008 22:01

Vedernikoff Sergey wrote 15 September 2007 04:23

You should use such structure, as RSQ...

What is it - RSQ?

Re: Time Limit on test 17 (Pascal)

Posted by [USTU to be] Kirill Teplinskiy 7 Dec 2008 23:11

no nevermind
RSQ doesn't necessary
Try to imagine that all what you know - it's how to sum numbers.

Edited by author 07.12.2008 23:11

Re: Time Limit on test 17 (Pascal)

Posted by svr 7 Dec 2008 23:18

Simple O(N) problem
RSO is humiliation.

Re: Time Limit on test 17 (Pascal)

Posted by Vedernikoff Sergey (HSE: EconomicsForever!) 8 Dec 2008 03:28

What humiliation do you mean? Humiliation of whom?

Re: Time Limit on test 17 (Pascal)

Posted by svr 8 Dec 2008 09:19

It doesn't matter, simply so seems to me.

Discussion of Problem 1491. Unreal Story