/**
* author: m371
* created: 29.10.2021 14:34:19
**/
#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
int putaway(int a, int b, int t, int* x, int* y, int* w, int* s) {
vector<int> ord_x(a);
iota(ord_x.begin(), ord_x.end(), 0);
sort(ord_x.begin(), ord_x.end(), [&](int i, int j) {
return x[i] < x[j];
});
vector<int> ord_y(b);
iota(ord_y.begin(), ord_y.end(), 0);
sort(ord_y.begin(), ord_y.end(), [&](int i, int j) {
return y[i] < y[j];
});
vector<int> ord_w(t);
iota(ord_w.begin(), ord_w.end(), 0);
sort(ord_w.begin(), ord_w.end(), [&](int i, int j) {
return w[i] < w[j];
});
vector<int> ord_s(t);
iota(ord_s.begin(), ord_s.end(), 0);
sort(ord_s.begin(), ord_s.end(), [&](int i, int j) {
return s[i] < s[j];
});
auto Can = [&](int S) {
int ptr = 0;
priority_queue<pair<int, int>> st;
vector<bool> was(t, false);
for (int i = 0; i < a; i++) {
while (ptr < t && w[ord_w[ptr]] < x[ord_x[i]]) {
st.push({s[ord_w[ptr]], ord_w[ptr]});
ptr++;
}
int cnt = 0;
while (!st.empty() && cnt < S) {
pair<int, int> it = st.top();
was[it.second] = true;
cnt += 1;
st.pop();
}
}
while (!st.empty()) {
st.pop();
}
ptr = 0;
for (int i = 0; i < b; i++) {
while (ptr < t && s[ord_s[ptr]] < y[ord_y[i]]) {
if (!was[ord_s[ptr]]) {
st.push({w[ord_s[ptr]], ord_s[ptr]});
}
ptr++;
}
int cnt = 0;
while (!st.empty() && cnt < S) {
pair<int, int> it = st.top();
was[it.second] = true;
cnt += 1;
st.pop();
}
}
for (int i = 0; i < t; i++) {
if (!was[i]) {
return false;
}
}
return true;
};
if (!Can(t)) {
return -1;
}
int low = 1, high = t, ans = 0;
while (low <= high) {
int mid = (low + high) >> 1;
if (Can(mid)) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans;
}
