/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include"robots.h"
#include <map>
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <cstdio>
#define maxn 2000005
#define maxn2 205
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cerr<<"passed"<<endl;
#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")
using namespace std;
/**std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;
double timePassed()
{
using namespace std::chrono;
currT = high_resolution_clock::now();
double time = duration_cast<duration<double>>(currT - startT).count();
return time * TIME_MULT;
}*/
typedef pair <int, int> pii;
int a , b , t;
int w[maxn] , s[maxn];
int x[maxn] , y[maxn];
pii pom[maxn];
bool check(int time)
{
int pomm = 1 , idx = a - 1;
map <int , int> m;
for(int i = 0; i < b; i++)
m[i] = time;
long long tt = 0;
for(int i = t - 1; i > -1; i--)
{
while(idx > -1 && idx >= pom[i].X)
{
idx--;
tt += time;
}
auto it = m.lower_bound(pom[i].Y);
if(it == m.end())
tt--;
else
{
--((*it).Y);
if((*it).Y == 0)
m.erase(it);
}
if(tt < 0)
{
pomm = 0;
break;
}
}
return pomm;
}
int putaway(int A , int B , int T , int X[] , int Y[] , int W[] , int S[])
{
a = A;
b = B;
t = T;
for(int i = 0; i < t; i++)
{
w[i] = W[i];
s[i] = S[i];
}
for(int i = 0; i < a; i++)
x[i] = X[i];
for(int i = 0; i < b; i++)
y[i] = Y[i];
sort(x , x + a);
sort(y , y + b);
for(int i = 0; i < t; i++)
pom[i] = {upper_bound(x , x + a , w[i]) - x , upper_bound(y , y + b , s[i]) - y};
sort(pom , pom + t);
int l = 1;
int r = t + 1;
int mid;
while(l < r)
{
mid = (l + r) / 2;
if(check(mid) == true)
r = mid;
else
l = mid + 1;
}
if(l == t + 1)
return -1;
return l;
}
/**int main()
{
#ifdef ONLINE_JUDGE /// promeni
freopen("input.in", "r", stdin);
freopen("taxi.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//startT = std::chrono::high_resolution_clock::now();
return 0;
}*/
