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

Обсуждение задачи 1330. Интервалы

Time limit Exceed on 20 test. Why?
Послано Crusader 3 июн 2005 21:23
How to do my program more simply? Who khow?
When I send this program - Time limit Exceed on 20 test.
Help, who can!

Program zadacha;
var a:array[1..10000] of integer; b,c,i,j,n:integer; d:array[0..100000] of longint; m:longint;
begin
readln(n);
for i:=1 to n do
 read(a[i]);

readln(m);
for i:=1 to m do begin
 read(b,c);
  for j:=b to c do
   d[i]:=d[i]+a[j];
 end;
for i:=1 to m do
writeln(d[i]);
end.
Re: Time limit Exceed on 20 test. Why?
Послано Виктор Крупко 3 июн 2005 23:28
100.000 * 10.000 = 1.000.000.000
change algoritm (he easy)
Re: Time limit Exceed on 20 test. Why?
Послано Crusader 4 июн 2005 13:47
Виктор Крупко писал(a) 3 июня 2005 23:28
100.000 * 10.000 = 1.000.000.000
change algoritm (he easy)
So, what algoritm must I use there? Can you tell me?
S[i..j] = S[1..j] - S[1..i-1] (-)
Послано Dmitry 'Diman_YES' Kovalioff 4 июн 2005 19:47
Re: S[i..j] = S[1..j] - S[1..i-1] (-)
Послано Crusader 7 июн 2005 11:13
I don't understand. Please, write once again.
see+++++++++++++
Послано Виктор Крупко 8 июн 2005 01:10
6
4
2
3
1
5
7
2
2 4
3 5 {k,n}

answer:
(4+2+3+1)-(4)=6
(4+2+3+1+5)-(4+2)=9


Clearly: a[n]-a[k-1]
Re: S[i..j] = S[1..j] - S[1..i-1] (-)
Послано Ikrom 7 май 2008 18:51
Thank you very much.
Re: see+++++++++++++
Послано yzlhm 9 фев 2009 08:28
that is to amazing
Re: S[i..j] = S[1..j] - S[1..i-1] (-)
Послано Googologist 4 авг 2015 19:46
I don't see if it works faster than summing from i to j directly. Summing from 1 to j requires more work and then we yet have to compute another sum and subtract.