13_Gs9. Устройство [http://dl.gsu.by/task.jsp?nid=1122881&cid=620]

Это стандартная задача на использование кучи.
Вводим число и помещаем его в кучу, по запросу (число=0), берём из кучи минимальный.

В С+\+ для реализации кучи можно использовать multiset
( не set, поскольку в данной задаче элементы могут повторяться)
{code:title=p.cpp|borderStyle=solid}
#include <bits/stdc++.h>
using namespace std;

int main()
{
multiset<int> s;
int N,i,a;

cin >> N ;
for (i=0; i<N; i++)
{
cin >> a;
if (a) s.insert(a);
else {
a=*s.begin();
cout << a << endl;
s.erase(s.find(a));
}
}
}
{code}
13_NovS. CROWDED
[http://dl.gsu.by/task.jsp?nid=1237652&cid=130]
Простейший вариант реализации
- сортируем по возрастанию x
Для каждой точки i выясняем тесно ей или нет следующим образом:
кидаем в set H1 высоты всех точек, которые лежат слева от I на расстоянии не больше чем D
кидаем в set H2 высоты всех точек, которые лежат справа от I на расстоянии не больше чем D
Если оба сета не пусты и оба максимума больше удвоенной высоты текущей точки,
то инкрементируем ответ
{code:title=p.cpp|borderStyle=solid}
#include <bits/stdc++.h>
using namespace std;

int main() {
freopen("crowded.in", "r", stdin);
freopen("crowded.out", "w", stdout);

int N, D;
cin >> N >> D;

vector<pair<int, int> > A(N);
for(int i = 0; i < N; i++)
cin >> A[i].first >> A[i].second;

sort(A.begin(), A.end());

int j1,j2,result = 0;
for(int i = 0; i < N; i++)
{
set<int> H1, H2;
j1=i-1;
while(j1 >= 0 && A[j1].first >= A[i].first - D) H1.insert(A[j1--].second);
j2=i+1;
while(j2 < N && A[j2].first <= A[i].first + D) H2.insert(A[j2++].second);
if ((not H1.empty() && *--H1.end() >= 2 * A[i].second &&
(not H2.empty() && *--H2.end() >= 2 * A[i].second)) ) result++;
}
cout << result;
}
{code}

проходит только 5 тестов

попробуем оптимизировать работу с сетами
ведь при переходе от точки I к следующей можно просто удалять не нужные и добавлять нужные элементы:

а именно

при переходе к следующей точке I
в правом сете (H2) добавляем все подходящие, а удаляем - i-ую вершину
в левом сете (H1) добавляем i-1-ую вершину и удаляем все не подходящие

Вводим вектором массив координат x и h
{quote}
vector<pair<int, int> > A(N);
for(int i = 0; i < N; i++)
cin >> A\[i\].first >> A\[i\].second;
{quote}
Это позволяет сортировать эти два массива x и h параллельно стандартной сортировкой
{quote}
sort(A.begin(), A.end());
{quote}
Заводим мультимножества (множества, которые могут содержать одинаковые элементы) H1 и H2
{quote}
multiset<int> H1, H2;
{quote}
Далее в цикле для всех точек в порядке возрастания по x
{code:title=part.cpp|borderStyle=solid}
int j = 0, k = 0, result = 0;
for(int i = 0; i < N; i++)
{
while (j2 < N && A[j2].first-A[i].first <= D) H2.insert(A[j2++].second);
Пока точки с индексом j2 в диапазоне D справа от точки I, добавляем их высоты в H2

H2.erase(A[i].second);
Удаляем из H2 высоту точки i

if (i>0) H1.insert(A[i-1].second);
Если точка не крайняя слева, добавляем в H1 высоту предыдущей точки

while (j1 < i && A[i].first-A[j1].first > D) H1.erase (A[j1++].second);
Пока точки с индексом j1 вне диапазона D слева от точки I удаляем их из H1


if ((not H1.empty() && *--H1.end() >= 2 * A[i].second &&
(not H2.empty() && *--H2.end() >= 2 * A[i].second)) ) result++;
Если последний элемент в H1 >= 2*h[i] и
Последний элемент в H2 >= 2*h[i] - инкрементируем ответ

Последний элемент в мультимножестве, упорядоченном по возрастанию
- это самый большой
}
cout << result;
}
{code}
Полный текст решения
{code:title=all.cpp|borderStyle=solid}
#include <bits/stdc++.h>
using namespace std;

int main() {
freopen("crowded.in", "r", stdin);
freopen("crowded.out", "w", stdout);

int N, D;
cin >> N >> D;

vector<pair<int, int> > A(N);
for(int i = 0; i < N; i++)
cin >> A[i].first >> A[i].second;

sort(A.begin(), A.end());

set<int> H1, H2;
int j1=0,j2=0,result = 0;
for(int i = 0; i < N; i++)
{
while (j2 < N && A[j2].first-A[i].first <= D) H2.insert(A[j2++].second);
H2.erase(A[i].second);
if (i>0) H1.insert(A[i-1].second);
while (j1 < i && A[i].first-A[j1].first > D) H1.erase (A[j1++].second);
if ((not H1.empty() && *--H1.end() >= 2 * A[i].second &&
(not H2.empty() && *--H2.end() >= 2 * A[i].second)) ) result++;
}
cout << result;
}
{code}