Как ускорить выполнение кода в консольном приложении?

Question

Нужно придумать, как ускорить выполнение вот этого кода (консольное приложение).

    public static void Main(string[] args)
    {
    
        string[] line = Console.ReadLine().Split(' ');
        int n = Int32.Parse(line[0]); 
        int m = Int32.Parse(line[1]); 
        
        int [] cells = new int[n]; 

        for(int i=0; i<m; i++){  
            string[] line1 = Console.ReadLine().Split(' ');
            int l = Int32.Parse(line1[0]); 
            int r = Int32.Parse(line1[1]);   
            int c = Int32.Parse(line1[2]);
            
            Array.Fill(cells, c, l-1, r-l+1);
        }

        Console.WriteLine( String.Join(" ", cells ));
    }

Это решение вот этой задачи. Может, как-то иначе можно было решить?

Вот перевод этой задачи:

Юный художник

Ограничение: 1 сек., 256 МиБ

Юный художник Зеник имеет n последовательно расположенных белых ячеек, пронумерованных от 1 до n слева направо, которые можно окрашивать.

Он выполняет m покрасок такого вида: (l,r,c) — закрасить все ячейки от l до r включительно в цвет c. Каждая ячейка окрашена только в последний цвет, которым окрашивалась соответствующая ячейка.

Вам нужно восстановить конечную картину, то есть определить цвет всех ячеек после выполнения всех запросов.

Входные данные В первой строке задано два целых числа n и m — количество ячеек и количество окрасок.

В следующих m строках задано по 3 целых числа l, r и c

соответствующая покраска.

Выходные данные

В единственной строке выведите n целых чисел через пробел – цвета ячеек после всех окрасок. Считайте, что белый цвет – это 0.

Answer 1

Если n = m = 10⁵ и все запросы красят все ячейки, программа работает около десяти секунд. Если закомментировать вызов Array.Fill, программа работает быстрее 0.2c. Ускоряя ввод/вывод мы можем выиграть 0.2с. Этого недостаточно чтобы уложиться в ограничения по времени. Надо ускорять алгоритм.

Текущий алгоритм работает за O(mn) в худшем случае.

Задачу можно решить быстрее заметанием по номеру ячейки. Каждый запрос на рисование превращается в два события - начало и конец отрезка, который закрашивается. Все события сортируются по позициям. По событиям проводится заметание. В статусе все запросы, которые красят текущую позицию. Позиция окрашивается в цвет запроса у которого максимальный номер (в цвет последнего запроса). При обработке события статус обновляется за O(log(m)). За тоже время из статуса извлекается последний запрос. Статус хранится в SortedSet.

Общая сложность по времени O(m·log(m) + n), по памяти O(m).

Пример для следующего входа:

События:

   Запрос    начальное событие    конечное событие
i  l r c     (l, true, i, c)      (r+1, false, i, c)

0  1 4 7     (1, true, 0, 7)      (5  , false, 0, 7)
1  6 6 1     (6, true, 1, 1)      (7  , false, 1, 1) 
2  4 6 2     (4, true, 2, 2)      (7  , false, 2, 2)
3  5 7 1     (5, true, 3, 1)      (8  , false, 3, 1)

События упорядочиваются по первому значению. Если событие соответствует началу отрезка, в статус добавляется пара из номера запроса и цвета. Событие конца удаляет соответствующую пару.

Все ячейки между двумя соседними событиями окрашиваются в цвет последнего по времени запроса в статусе. Статус упорядочен по номерам запросов, цвет берётся из самого правого элемента - последнего по времени запроса:

Событие             Статус                      Окраска
(p, start, i, c)    {(i, c), ...}               c -> [l, r)

                    {}                          -
(1, true , 0, 7)
                    {(0, 7)}                    7 -> [1, 4)
(4, true , 2, 2)
                    {(0, 7), (2, 2)}            2 -> [4, 5)
(5, false, 0, 7)
                    {(2, 2)}                    2 -> [5, 5)
(5, true , 3, 1)
                    {(2, 2), (3, 1)}            1 -> [5, 6)
(6, true , 1, 1)
                    {(1, 1), (2, 2), (3, 1)}    1 -> [6, 7)
(7, false, 1, 1) 
                    {(2, 2), (3, 1)}            1 -> [7, 7)
(7, false, 2, 2)
                    {(3, 1)}                    1 -> [7, 8)
(8, false, 3, 1)
                    {}                          -

Помимо описанного в примере, программа до начала заметания добавляет событие на правом конце картины и нулевой цвет в статус. Это нужно чтобы те места картины где нет запросов (то есть статус пуст) были закрашены нулевым цветом.

В худшем случае новая версия работает быстрее чем за 0.6c.

using System;
using System.Collections.Generic;

using Pair = System.Collections.Generic.KeyValuePair<int, int>;

public class Temp {
    public static void Main(string[] args) {
        string[] line = Console.ReadLine().Split(' ');
        int n = Int32.Parse(line[0]); 
        int m = Int32.Parse(line[1]); 
        
        // position, start?, request, color
        var events = new (int, bool, int, int)[2 * m + 1]; 

        for (int i = 0; i < m; ++i) {  
            string[] line2 = Console.ReadLine().Split(' ');
            int left  = Int32.Parse(line2[0]); 
            int right = Int32.Parse(line2[1]);   
            int color = Int32.Parse(line2[2]);
            events[2 * i    ] = (left     , true , i, color);
            events[2 * i + 1] = (right + 1, false, i, color);
        }
        events[2 * m] = (n + 1, false, -1, 0);

        Array.Sort(events);

        // request, color
        var requests = new SortedSet<Pair>(
            Comparer<Pair>.Create((x, y) => x.Key.CompareTo(y.Key))
        );
        requests.Add(new Pair(-1, 0));

        int prevPosition = 1;
        foreach (var e in events) {
            var (position, start, request, color) = e;
            int cp = requests.Max.Value;
            for (int i = prevPosition; i < position; ++i) {
                Console.Write(cp + " ");
            }
            prevPosition = position;
            var pair = new Pair(request, color);
            if (start) {
                requests.Add(pair);
            } else {
                requests.Remove(pair);
            }
        }
        Console.WriteLine();
    }
}

БЛОГ НА HUSL

Как ускорить выполнение кода в консольном приложении?

Ответы (1 шт):