Решение

Тема: дерево максимумов, сортировка или списки
Сложность: высокая

Сначала нужно отсортировать начала и концы отрезков, соответствующей попытке гнома покрасить забор. В C/C++ можно использовать стандартную функцию qsort/sort, в Pascal нужно либо написать эту функцию самостоятельно, либо реализовать более простой алгоритм сортировки расстановкой. Значения с одинаковым ключом храним в виде списков.

var 
  sl:array [1..100001] of integer; 
  tries:array [1..100000] of record
    color:char; 
    i,j:integer;
    nexti,nextj:integer;
  end;
  N,M,i,j,k,p:integer;
...
readln(N,M);
for i:=1 to M do
begin
  readln(tries[i].color,tries[i].i,tries[i].j);
  tries[i].nexti:=sl[tries[i].i];
  sl[tries[i].i]:=i;
  tries[i].nextj:=sl[tries[i].j+1];
  sl[tries[i].j+1]:=i;
end; 

Далее используем дерево максимумов, в котором в ячейке `i` хранится максимальное из чисел в ячейках `2*i` и `2*i+1`. Неиспользуемые ячейки дерева помечаются значением 0. Листья дерева располагаются все на одном уровне и начинаются с ячейки 131072 (`=2^17`, первая степень двойки большая `10^5`). При обработке начала `k`-й попытки гнома покрасить забор, значение `k` в помещается ячейку (131071+`k`), при обработке конца попытки – в эту ячейку помещается 0.

var maxtree:array[1..262144] of integer;
...
for i:=1 to N do
begin
  j:=sl[i];
  while j<>0 do
  begin
    k:=j+131071;
    if tries[j].i=i then
      maxtree[k]:=j
    else      
      maxtree[k]:=0;
    while k>1 do
    begin
      p:=k div 2;
      if maxtree[2*p]>maxtree[2*p+1] then
        maxtree[p]:=maxtree[2*p]
      else
        maxtree[p]:=maxtree[2*p+1];
      k:=p;
    end;
    if tries[j].i=i then
      j:=tries[j].nexti
    else
      j:=tries[j].nextj;
  end;
  if maxtree[1]=0 then
    write('.')
  else
    write(tries[maxtree[1]].color);
end;
writeln;

В C++ вместо дерева максимумов можно использовать стандартный класс set.