Если n = m = 105 и все запросы красят все ячейки, программа работает около десяти секунд. Если закомментировать вызов Array.Fill, программа работает быстрее 0.2c. Ускоряя ввод/вывод мы можем выиграть 0.2с. Этого недостаточно чтобы уложиться в ограничения по времени. Надо ускорять алгоритм.
Текущий алгоритм работает за O(mn) в худшем случае.
Задачу можно решить быстрее заметанием по номеру ячейки. Каждый запрос на рисование превращается в два события - начало и конец отрезка, который закрашивается. Все события сортируются по позициям. По событиям проводится заметание. В статусе все запросы, которые красят текущую позицию. Позиция окрашивается в цвет запроса у которого максимальный номер (в цвет последнего запроса). При обработке события статус обновляется за O(log(m)). За тоже время из статуса извлекается последний запрос. Статус хранится в SortedSet.
Общая сложность по времени O(m·log(m) + n), по памяти O(m).
Пример для следующего входа:
7 4
1 4 7
6 6 1
4 6 2
5 7 1
События:
Запрос начальное событие конечное событие
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();
}
}