G
G
GONJY MONJY2020-10-11 16:27:26
Pascal
GONJY MONJY, 2020-10-11 16:27:26

How to speed up program calculations?

Hello! There is such a problem:

You have N keys and M locks, the keys are numbered with integers from 1 to N, and the locks are numbered with integers from 1 to M. The lock with number i can be opened by all keys with numbers from Li to Ri. How many keys can open all locks?

Input format
The first line contains two numbers N, M (1 ≤ N, M ≤ 2 ⋅ 10^5). Each of the next M lines contains two integers Li, Ri (1 ≤ Li ≤ Ri ≤ N).

Output Format
Output the number of keys that can open all locks.

Example 1
Input
4 2
1 3
2 4

Output
2

Example 2
Input
10 3
3 6
5 7
6 9

Output
1

Example 3
Input
100000 1

Output
100000

Memory limit: 256 MB.
Time limit: 1 second.

This is what my code looks like:

uses crt;
var i, j, d: longint;
    k, v, s, f: longint;
    n, m: 1..250000;
    key1, key2: 1..250000;
    a: array [1..300000] of longint;
    r: array [1..300000] of longint;
    l: array [1..300000] of longint;
begin
read(n, m);
s:=1;

for i:=1 to m do
 begin
  read(key1, key2);
  r[i]:=key1; l[i]:=key2;
  for j:=r[i] to l[i] do
   begin
    f:=f+1;
    a[s]:=j;
    s:=s+1;
  end;
end;

if (m = 1) then writeln(l[1])
else
 begin
  while 1 <= f do
   begin
    s:=0;
    i:=1;
    v:=f;
    k:=a[1];

    while i <= v do
     begin
      if a[i] = k then
       begin
        s:=s+1;
        for j:=i to v-1 do
         a[j]:=a[j+1];
         v:=v-1
      end else i:=i+1;
    end;

    if (s mod m = 0) then d:=d+1;
    f:=f-s;
  end;

  writeln(d);
end;

end.


For small numbers, it works in the region of up to a second, but for large numbers it is already more than necessary. I analyze the Olympiad problems of the 8th grade, so it is desirable to have the code as it would be solved by a student of the 8th grade.

Answer the question

In order to leave comments, you need to log in

1 answer(s)
V
Vasily Bannikov, 2020-11-29
@vabka

1. We describe the algorithm in a more or less understandable form (for example, in pseudocode)
2. We read about big-o notation in order to understand where our bottlenecks are
3. We read about data structures.
4. Trying to get rid of unnecessary cycles
For 2 and 3, you can read "Groaking algorithms" and "Algorithms, their construction and analysis".
>how would a 8th grade student solve it
A 8th grade student who knows about algorithms will be able to come up with a very effective solution, only his code will most likely be shit)

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question