Обсуждение @ 1491. Нереальная история @ Timus Online Judge

Time Limit on test 17 (Pascal)

Послано Assassin 14 сен 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)

Послано Vedernikoff Sergey 15 сен 2007 04:23

You should use such structure, as RSQ...

Re: Time Limit on test 17 (Pascal)

Послано Tolstobrov Anatoliy[Ivanovo SPU] 15 сен 2007 07:34

O(N) possible

Re: Time Limit on test 17 (Pascal)

Послано Howl of Despair 6 фев 2008 22:01

Vedernikoff Sergey писал(a) 15 сентября 2007 04:23

You should use such structure, as RSQ...

What is it - RSQ?

Re: Time Limit on test 17 (Pascal)

Послано [USTU to be] Kirill Teplinskiy 7 дек 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)

Послано svr 7 дек 2008 23:18

Simple O(N) problem
RSO is humiliation.

Re: Time Limit on test 17 (Pascal)

Послано Vedernikoff Sergey (HSE: EconomicsForever!) 8 дек 2008 03:28

What humiliation do you mean? Humiliation of whom?

Re: Time Limit on test 17 (Pascal)

Послано svr 8 дек 2008 09:19

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

Обсуждение задачи 1491. Нереальная история