ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

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

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.