#include <bits/stdc++.h>
#include "robots.h".
//#include "grader.h"
using namespace std;
#define ll long long
#define F first
#define S second
mt19937 rnd(100);
int putaway(int N, int M, int K, int X0[], int Y0[], int PX[], int PY[]) {
multiset<int> X, Y;
for (int i = 0; i < N; i++)
X.insert(X0[i] - 1);
for (int i = 0; i < M; i++)
Y.insert(Y0[i] - 1);
for (int i = 0; i < K; i++)
if (X.lower_bound(PX[i]) == X.end() && Y.lower_bound(PY[i]) == Y.end())
return -1;
map<int, multiset<pair<int, int>>*> ver, hor;
for (int i = 0; i < K; i++)
{
int h = *X.lower_bound(PX[i]);
if (!ver.count(h))
ver[h] = new multiset<pair<int, int>>;
ver[h]->insert({PY[i], PX[i]});
h = *Y.lower_bound(PY[i]);
if (!hor.count(h))
hor[h] = new multiset<pair<int, int>>;
hor[h]->insert({PX[i], PY[i]});
}
int ans = 0;
while (K) {
for (int x : X) { // Перебираем вертикальную прямую.
auto p0 = ver.upper_bound(x);
if (p0 == ver.begin())
continue;
--p0;
pair<int, int> p = *prev(p0->S->end()); // Удаляемая пара (y x)
p0->S->erase(p);
if (p0->S->empty())
ver.erase(p0);
int h = *Y.lower_bound(p.F);
if (!hor.count(h))
hor[h] = new multiset<pair<int, int>>;
hor[h]->erase({p.S, p.F});
if (hor[h]->empty())
hor.erase(h);
K--;
}
for (int y : Y) {
auto p0 = hor.upper_bound(y);
if (p0 == hor.begin())
continue;
--p0;
pair<int, int> p = *prev(p0->S->end()); // Удаляемая пара (x y)
p0->S->erase(p);
if (p0->S->empty())
hor.erase(p0);
int h = *X.lower_bound(p.F);
if (!ver.count(h))
ver[h] = new multiset<pair<int, int>>;
ver[h]->erase({p.S, p.F});
if (ver[h]->empty())
ver.erase(h);
K--;
}
ans++;
}
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int N, M, K;
cin >> N >> M >> K;
int X[N], Y[M], PX[K], PY[K];
for (int &i : X)
cin >> i;
for (int &i : Y)
cin >> i;
for (int i = 0; i < K; i++)
cin >> PX[i] >> PY[i];
cout << putaway(N, M, K, X, Y, PX, PY);
}*/
/*
3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
2 1 3
2 5
3
3 1
5 3
2 2
*/
/*
*/
/*
Ох. Я конечно стер предыдущие большие мысли, но все еще выглядит как жадник.
Для каждой вертикальной прямой есть элементы которые находятся в самом правом доступном для этой прямой столбце.
Из них мы берем максимальный по другому параметру элемент.
Правда ли это? Подумаю над контр тестом.
Ладно. Можно сначала в тупую написать.
Можно максимально в тупую. Нужно идею проверить.
Для каждой точки найдем первую прямую справа.
Разделим точки по признаку такой прямой.
При обработке удаления от прямой, мы берем множество для самой правой из прямых левее и удаляем максимальную по второй координате точку оттуда.
Вопрос появился.
Важно ли для прямых одного типа то, как по ним проходиться?
Ну, вдруг да, будем проходиться снизу вверх.
*/
/*
*/
/*
*/
/*
*/
/*
10 _ _ | _ _ _ _ | _ _ _ | _
9 _ _ | _ _ _ _ | 3 _ _ | _
8 4 _ | _ _ _ _ | _ _ _ | _
---------------------------------------
7 _ _ | _ _ _ _ | _ 7 _ | _
6 _ _ | _ 0 _ _ | 8 _ _ | _
5 _ _ | _ _ _ _ | _ 1 _ | 9
---------------------------------------
4 _ _ | _ _ _ _ | _ _ _ | _
3 _ 2 | 6 _ _ _ | _ _ _ | _
2 _ _ | _ _ _ _ | _ _ _ | _
1 _ _ | _ _ 5 _ | _ _ _ | _
1 2 3 4 5 6 7 8 9 10
10 _ _ | _ _ _ _ | _ _ _ | _
9 _ _ | _ _ _ _ | _ _ _ | _
8 _ _ | _ _ _ _ | _ _ _ | _
---------------------------------------
7 _ _ | _ _ _ _ | _ 7 _ | _
6 _ _ | _ _ _ _ | 8 _ _ | _
5 _ _ | _ _ _ _ | _ 1 _ | _
---------------------------------------
4 _ _ | _ _ _ _ | _ _ _ | _
3 _ 2 | _ _ _ _ | _ _ _ | _
2 _ _ | _ _ _ _ | _ _ _ | _
1 _ _ | _ _ 5 _ | _ _ _ | _
1 2 3 4 5 6 7 8 9 10
10 _ _ | _ _ _ _ | _ _ _ | _
9 _ _ | _ _ _ _ | _ _ _ | _
8 _ _ | _ _ _ _ | _ _ _ | _
---------------------------------------
7 _ _ | _ _ _ _ | _ _ _ | _
6 _ _ | _ _ _ _ | _ _ _ | _
5 _ _ | _ _ _ _ | _ 1 _ | _
---------------------------------------
4 _ _ | _ _ _ _ | _ _ _ | _
3 _ _ | _ _ _ _ | _ _ _ | _
2 _ _ | _ _ _ _ | _ _ _ | _
1 _ _ | _ _ _ _ | _ _ _ | _
1 2 3 4 5 6 7 8 9 10
*/
