#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
int maxVec( int n, int* v ) {
int x = 0;
for ( int i = 0; i < n; i ++ ) {
x = max( x, v[i] );
}
return x;
}
unordered_map <int, int> cod;
void normalize( vector <int> values ) {
cod.clear();
sort( values.begin(), values.end() );
cod[values[0]] = 1;
for ( int i = 1; i < values.size(); i ++ ) {
if ( values[i] != values[i - 1] ) cod[values[i]] = cod[values[i - 1]] + 1;
}
}
void normVec( int n1, int n2, int v1[], int v2[] ) {
vector <int> values;
for ( int i = 0; i < n1; i ++ ) values.push_back( v1[i] );
for ( int i = 0; i < n2; i ++ ) values.push_back( v2[i] );
normalize( values );
for ( int i = 0; i < n1; i ++ ) v1[i] = cod[v1[i]];
for ( int i = 0; i < n2; i ++ ) v2[i] = cod[v2[i]];
}
int sumRect( const vector<vector<int>>& a, int l1, int c1, int l2, int c2 ) {
return a[l2][c2] - a[l2][c1 - 1] - a[l1 - 1][c2] + a[l1 - 1][c1 - 1];
}
int tavan( int a, int b ) {
if ( b == 0 ) {
if ( a == 0 ) return 0;
return 1e9;
}
return ( a - 1 ) / b + 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[] ) {
normVec( A, T, X, W );
normVec( B, T, Y, S );
int maxX = maxVec( A, X ), maxY = maxVec( B, Y );
for ( int i = 0; i < T; i ++ ) {
if ( W[i] > maxX && S[i] > maxY ) return -1;
}
vector <vector<int>> sum( maxX + 2 );
for ( int i = 0; i <= maxX + 1; i ++ ) sum[i].resize( maxY + 2 );
for ( int i = 0; i < T; i ++ ) sum[min( W[i], maxX + 1 )][min( S[i], maxY + 1 )] = 1;
for ( int i = 1; i <= maxX + 1; i ++ ) {
sum[i][0] += sum[i - 1][0];
}
for ( int i = 1; i <= maxY + 1; i ++ ) {
sum[0][i] += sum[0][i - 1];
}
for ( int i = 1; i <= maxX + 1; i ++ ) {
for ( int j = 1; j <= maxY + 1; j ++ ) {
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
int ans = ( T - 1 ) / ( A + B ) + 1;
for ( int i = 0; i < A; i ++ ) {
ans = max( ans, tavan( sumRect( sum, X[i] + 1, 1, maxX + 1, maxY + 1 ), A - i - 1 + B ) );
for ( int j = 0; j < B; j ++ ) {
int rap = tavan( sumRect( sum, X[i] + 1, Y[j] + 1, maxX + 1, maxY + 1 ), A - i + B - j - 2 );
ans = max( ans, rap );
}
}
return ans;
}
