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

Crusader Time limit Exceed on 20 test. Why? [8] // Problem 1330. Intervals 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.
ACM.Krupko_Victor[Ivanovo SPU] Re: Time limit Exceed on 20 test. Why? [7] // Problem 1330. Intervals 3 Jun 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] // Problem 1330. Intervals 4 Jun 2005 13:47
ACM.Krupko_Victor[Ivanovo SPU] 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?
Dmitry 'Diman_YES' Kovalioff. Retired S[i..j] = S[1..j] - S[1..i-1] (-) [5] // Problem 1330. Intervals 4 Jun 2005 19:47
Crusader Re: S[i..j] = S[1..j] - S[1..i-1] (-) [2] // Problem 1330. Intervals 7 Jun 2005 11:13
I don't understand. Please, write once again.
ACM.Krupko_Victor[Ivanovo SPU] see+++++++++++++ [1] // Problem 1330. Intervals 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]
cherudim Re: see+++++++++++++ // Problem 1330. Intervals 9 Feb 2009 08:28
that is to amazing
bob Re: S[i..j] = S[1..j] - S[1..i-1] (-) [1] // Problem 1330. Intervals 7 May 2008 18:51
Thank you very much.
Googologist Re: S[i..j] = S[1..j] - S[1..i-1] (-) // Problem 1330. Intervals 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.