GONJY_MONJY
@GONJY_MONJY
В поисках новых горизонтов

Как ускорить вычисления программы?

Здравствуйте! Есть такая задачка:

У вас есть N ключей и M замков, ключи пронумерованы целыми числами от 1 до N, а замки пронумерованы целыми числами от 1 до M. Замок с номером i могут открыть все ключи с номерами от Li до Ri. Сколько ключей могут открыть все замки?

Формат ввода
В первой строке записаны два числа N, M (1 ≤ N, M ≤ 2 ⋅ 10^5). Каждая из следующих M строк содержит по два числа Li, Ri (1 ≤ Li ≤ Ri ≤ N).

Формат вывода
Выведите количество ключей, которые могут открыть все замки.

Пример 1
Ввод
4 2
1 3
2 4

Вывод
2

Пример 2
Ввод
10 3
3 6
5 7
6 9

Вывод
1

Пример 3
Ввод
100000 1

Вывод
100000

Лимит памяти: 256 мб.
Лимит времени: 1 секунда.

Вот так выглядит мой код:
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.


Для маленьких чисел работает в районе до секунды, но для больших чисел уже больше нужного. Разбираю олимпиадные задачи 8 класса, поэтому желательно код такой, как бы это решил ученик 8 класса.
  • Вопрос задан
  • 79 просмотров
Решения вопроса 1
vabka
@vabka
Токсичный шарпист
1. Описываем алгоритм в более-менее понятном виде (например псевдокодом)
2. Читаем про big-o notation, чтобы понять, где у нас узкие места
3. Читаем про структуры данных.
4. Пробуем избавиться от лишних циклов

Для 2 и 3 можно почитать "Грокаем алгоритмы" и "Алгоритмы, их построение и анализ".

>как бы это решил ученик 8 класса
Ученик 8го класса, знающий про алгоритмы сможет придумать очень эффективное решение, только код у него скорее всего говно будет)
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы