ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1330. Intervals

Show all messages Hide all messages

Time limit Exceed on 20 test. Why? Crusader 3 Jun 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 Jun 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 Jun 2005 13:47
Виктор Крупко wrote 3 June 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 Jun 2005 19:47
Re: S[i..j] = S[1..j] - S[1..i-1] (-) Crusader 7 Jun 2005 11:13
I don't understand. Please, write once again.
see+++++++++++++ Виктор Крупко 8 Jun 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: see+++++++++++++ yzlhm 9 Feb 2009 08:28
that is to amazing
Thank you very much.
Re: S[i..j] = S[1..j] - S[1..i-1] (-) Googologist 4 Aug 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.