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

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