07_AprS. City Horizon
[http://dl.gsu.by/task.jsp?nid=146092&cid=15]

Фермер Джон взял своих коров в город\! Коровы впервые увидели горизонт
в городе во время заката солнца на фоне прямоугольных зданий.
Этот горизонт определяется N (1 <= N <= 40,000) зданиями. Силуэт
здания i идет от A_i до B_i (1 <= A_i < B_i <= 1,000,000,000) на высоте
H_i (1 <= H_i <= 1,000,000,000).
Определите площадь (в квадратных единицах) общего силуэта,
сформированного всеми зданиями.

Формат ввода:
* Строка 1: Одно целое число: N

* Строки 2..N+1: Строка i+1 описывает здание i тремя разделенными
пробелами числами A_i B_i H_i

Пример ввода (файл horizon.in):

4
2 5 1
9 10 4
6 8 2
4 6 3

Формат вывода:
* Строка 1: Общая площадь, в квадратных единицах, силуэтов,
сформированных всеми N зданиями

Пример вывода (файл horizon.out):

16

OUTPUT DETAILS:

Первое здание перекрывается с четвертым зданием на площадь 1,
поэтому общая площадь есть 3*1 + 1*4 + 2*2 + 2*3 - 1 = 16.

Идея решения:

Заводим массив x координат начал и концов отрезков.
В массиве s для каждой такой точки храним, является ли она началом (Left=1) или концом (Right=2) отрезка.
В массиве h храним высоту этого отрезка.
kx - количество элементов в этом массиве

Сортируем массив x по возрастанию
(синхронно перемещаем элементы в массивах s и h)

Заводим массив актуальных высот hh (kh - количество элементов в нём).

Заносим туда первый элемент из h
Ответ = 0
Цикл по I от 2 до kx
Увеличиваем ответ на площадь прямоугольника (x\[i\]\-x\[i-1\])*MaxH
(здесь MaxH - максимум "актуальных высот" - максимум в hh)
Если s\[i\]=Left (начало отрезка)
То добавляем высоту этого отрезка в массив hh
иначе (конец отрезка) удаляем его высоту из списка актуальных высот
{code:title=p1.cpp|borderStyle=solid}
{$r-}
const
MaxN = 40000;
Left=1; Right=0;
var
X,H,HH,s : array [1..2*MaxN] of qword;
i,N,A,B,HA,kx,kh : longint;
Ans : qword;

procedure Put(xt,ht,LR:longint);
var
i : longint;
begin
inc(kx);
x[kx]:=xt; h[kx]:=ht; s[kx]:=LR;
end;
procedure Sort;
var
i,j,t : longint;
begin
for i:=1 to kx do
for j:=1 to kx-1 do
if x[j]>x[j+1]
then begin
t:=x[j]; x[j]:=x[j+1]; x[j+1]:=t;
t:=h[j]; h[j]:=h[j+1]; h[j+1]:=t;
t:=s[j]; s[j]:=s[j+1]; s[j+1]:=t;
end;
end;

procedure Add(h:longint);
begin
inc(kh); hh[kh]:=h;
end;

procedure Delete(h:longint);
var
i : longint;
begin
for i:=1 to kh do
if hh[i]=h then begin hh[i]:=0; exit; end;
end;

function MaxH:Qword;
var
i,max : longint;
begin
max:=0;
for i:=1 to kh do
if hh[i]>max then max:=hh[i];
MaxH:=max;
end;

begin
assign(input,'horizon.in'); reset(input);
assign(output,'horizon.out'); rewrite(output);
readln(N);
kx:=0;
for i:=1 to N do
begin
readln(A,B,HA);
Put(A,HA,Left);
Put(B,HA,Right);
end;
Sort;
Ans:=0; kh:=0;
Add(h[1]);
for i:=2 to kx do
begin
inc(Ans,(x[i]-x[i-1])*Maxh);
if s[i]=Left
then Add(h[i])
else Delete(h[i]);
end;
writeln(Ans);
close(input); close(output);
end.
{code}
Это решение прошло 8 тестов, но не прошло 2 последних теста по времени.
Заменим сортировку на быструю.
Всё равно последние два теста не прошли по времени.

Используем стандартные структуры C+\+ для хранения и обработки данных.
Для хранения всех троек (x, h, Left или Right) используем структуру данных Map
которая будет отображать x-координату точки в структуру вектор пар
- высота (h)
- признак левая/правая точка отрезка
(открывается или закрывается отрезок с высотой h в это точке )

Другими словами для каждой x-координаты из ввода Map будет хранить вектор пар чисел
(h,opens) (opens=1 - начало отрезка, open=0) конец отрезка

Объявление MAP с именем M
{noformat}
map<int,vector<pair<int,int> > > M;
{noformat}
Объявление переменной - итератора для MAP
{noformat}
map<int,vector<pair<int,int> > >::iterator im;
{noformat}
Ввод исходных данных и помещение их в MAP
{code:title=map.cpp|borderStyle=solid}
cin >> N;
while(N--)
{
cin >> a >> b >> h;
M[a].push_back(make_pair(h,1));
M[b].push_back(make_pair(h,0));
}
{code}
Итератор im затем используется для доступа к элементам, хранящимся в M:
{noformat}
for (im=M.begin(); im!=M.end(); im++)
{
...
{noformat}
При этом итератор для M по объявлению имеет два указателя
b = im->first
Первый указывает на очередную x-координату
(мы ее рассматриваем как конечную для текущего отрезка)
Начальная вначале 0 (a=0),
А каждый раз после обработки отрезка она становится следующей начальной (a=b)

J?каждой такой x-координатой, после ввода всех исходных данных,
связан вектор пар высота - признак начала/конца (открытия/закрытия) текущего отрезка.

Чтобы обрабатывать последовательно все элементы этого вектора объявляется
итератор вектора
{noformat}
vector<pair<int,int> >::iterator iv;
{noformat}
И он используется для организации соответствующего цикла:
{noformat}
for(iv=(im->second).begin(); iv!=(im->second).end(); iv++)
{
...

{noformat}
Для упорядоченного (по убыванию) хранения высот используем multiset S.
Объявление
{noformat}
multiset<int, greater<int> > S;
{noformat}
multiset S означает что числа в этом множестве могут повторяться
(по условию задачи высоты разных отрезков могут быть равны)
\\

Заметим, что в set числа не повторяются.

Для работы с multiset используем следующие функции:
S.insert(h) // вставить высоту h в S
S.erase(S.find(h)) // найти в S высоту h и удалить её
\*S.begin() // взять наибольшую высоту из S
Заметим, что наибольшая высота берётся за O(1),
а insert, find, erase выполняются за O(LogN)

Итак для обработки вектора (высота, признак) используется следующий цикл
{code:title=vektor.cpp|borderStyle=solid}
for(iv=(im->second).begin();iv!=(im->second).end();iv++)
{
h = iv->first;
opens = iv->second;
if(opens) S.insert(h);
else S.erase(S.find(h));
}
{code}
im->second - указатель в Map на этот вектор
iv - итератор в векторе
iv->first берёт первый элемент в текущей паре вектора пар
iv->second берёт второй элемент в текущей паре вектора пар

Если отрезок открывается, добавляем высоту в Multiset S
Иначе (отрезок закрывается), находим текущую высоту h в S и удаляем её оттуда

Полный текст решения:

{code:title=all.cpp|borderStyle=solid}
#include <bits/stdc++.h>
using namespace std;

map<int,vector<pair<int,int> > > M;
map<int,vector<pair<int,int> > >::iterator im;
vector<pair<int,int> >::iterator iv;
multiset<int, greater<int> > S;

int main()
{
int N,a,b,h,opens;
long long s=0;
freopen("horizon.in","r",stdin);
freopen("horizon.out","w",stdout);
cin >> N;
while(N--)
{
cin >> a >> b >> h;
M[a].push_back(make_pair(h,1));
M[b].push_back(make_pair(h,0));
}
a = 0;
for(im=M.begin();im!=M.end();im++)
{
b = im->first;
if(!S.empty()) s += (long long)(b - a)*(*S.begin());
a = b;
for(iv=(im->second).begin();iv!=(im->second).end();iv++)
{
h = iv->first;
opens = iv->second;
if(opens) S.insert(h);
else S.erase(S.find(h));
}
}
cout << s;
return 0;
}
{code}\\
\\