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

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

Crusader Time limit Exceed on 20 test. Why? [8] // Задача 1330. Интервалы 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? [7] // Задача 1330. Интервалы 3 июн 2005 23:28
100.000 * 10.000 = 1.000.000.000
change algoritm (he easy)
Crusader Re: Time limit Exceed on 20 test. Why? [6] // Задача 1330. Интервалы 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?
Dmitry 'Diman_YES' Kovalioff S[i..j] = S[1..j] - S[1..i-1] (-) [5] // Задача 1330. Интервалы 4 июн 2005 19:47
Crusader Re: S[i..j] = S[1..j] - S[1..i-1] (-) [2] // Задача 1330. Интервалы 7 июн 2005 11:13
I don't understand. Please, write once again.
Виктор Крупко see+++++++++++++ [1] // Задача 1330. Интервалы 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]
yzlhm Re: see+++++++++++++ // Задача 1330. Интервалы 9 фев 2009 08:28
that is to amazing
Ikrom Re: S[i..j] = S[1..j] - S[1..i-1] (-) [1] // Задача 1330. Интервалы 7 май 2008 18:51
Thank you very much.
Googologist Re: S[i..j] = S[1..j] - S[1..i-1] (-) // Задача 1330. Интервалы 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.