#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
int t;
vector<pair<int,int>> st;
void update(int pos, int val, int node=1, int tl=0, int tr=t-1){
if (tl == tr){
st[node] = {val, 1};
return;
}
int tm = (tl+tr)/2;
if (pos <= tm) update(pos, val, node*2, tl, tm);
else update(pos, val, node*2+1, tm+1, tr);
st[node] = {max(st[node*2].first, st[node*2+1].first), st[node*2].second+st[node*2+1].second};
}
int query(int val, int node=1, int tl=0, int tr=t-1){
if (st[node].first < val) return 0;
if (tl == tr) return st[node].second;
if (st[node*2+1].first < val) return query(val, node*2, tl, (tl+tr)/2);
else return st[node*2].second + query(val, node*2+1, (tl+tr)/2+1, tr);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
t = T;
st.resize(4*T, {0, 0});
vector<int> x, y;
vector<pair<int,int>> w, s;
//cout << "a" << endl;
for (int i=0; i<A; i++) x.push_back(X[i]);
for (int i=0; i<B; i++) y.push_back(Y[i]);
for (int i=0; i<T; i++){
w.push_back({W[i], i});
s.push_back({S[i], i});
}
//cout << "b" << endl;
sort(w.begin(), w.end());
reverse(w.begin(), w.end());
sort(s.begin(), s.end());
reverse(s.begin(), s.end());
unordered_map<int,int> um;
for (int i=0; i<T; i++) um[s[i].second] = i;
//cout << "c" << endl;
x.push_back(0); y.push_back(0);
sort(x.begin(), x.end());
reverse(x.begin(), x.end());
sort(y.begin(), y.end());
reverse(y.begin(), y.end());
vector<vector<int>> g(A+1);
//cout << "d" << endl;
for (int i=0; i<T; i++){
int l = -1, r = A;
while (l != r-1){
int m = (l+r)/2;
if (W[i] >= x[m]) r = m;
else l = m;
}
int l2 = -1, r2 = B;
while (l2 != r2-1){
int m = (l2+r2)/2;
if (S[i] >= y[m]) r2 = m;
else l2 = m;
}
//cout << r << " " << r2 << endl;
g[r].push_back(r2);
}
//cout << "e" << endl;
int res = 1;
int cur = 0;
for (int i=0; i<=A; i++){
while (cur != w.size() && w[cur].first >= x[i]){
update(um[w[cur].second], S[w[cur].second]);
cur++;
}
for (int j=0; j<=B; j++){
int ts = query(y[j]);
if (i+j == 0){
if (ts) return -1;
}
else res = max(res, (int) ceil((float) ts/ (float) (i+j)));
}
}
return res;
}
