#include "robots.h"
#include <string.h>
#define N 50000
#define M 50000
#define N_ (1 << 16) /* N_ = pow2(ceil(log2(M + 1))) */
#define K 1000000
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int *aa;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (aa[ii[j]] == aa[i_])
j++;
else if (aa[ii[j]] < aa[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
long long sum[N_ * 2], pref[N_ * 2]; int n_;
void pul(int i) {
int l = i << 1, r = l | 1;
sum[i] = sum[l] + sum[r], pref[i] = max(pref[l], sum[l] + pref[r]);
}
void build(int *ss, int k, int t) {
int h, i;
memset(sum + n_, 0, n_ * sizeof *sum);
for (h = 0; h < k; h++)
sum[n_ + ss[h]]++;
for (i = 0; i < n_; i++) {
if (i > 0)
sum[n_ + i] -= t;
pref[n_ + i] = max(sum[n_ + i], 0);
}
for (i = n_ - 1; i > 0; i--)
pul(i);
}
void decr(int i) {
i += n_;
pref[i] = max(--sum[i], 0);
while (i > 1)
pul(i >>= 1);
}
int solve(int *xx, int *ii, int n, int *ww, int *ss, int *hh, int k, int t) {
int h, i;
build(ss, k, t);
for (i = 0, h = 0; i <= n; i++) {
int x = i == 0 ? 0 : xx[ii[i - 1]];
while (h < k && ww[hh[h]] < x)
decr(ss[hh[h++]]);
if (pref[1] - (long long) (n - i) * t > 0)
return 0;
}
return 1;
}
int putaway(int n, int m, int k, int xx[], int yy[], int ww[], int ss[]) {
static int ii[N], jj[M], hh[K];
int h, i, j, lower, upper;
for (i = 0; i < n; i++)
ii[i] = i;
aa = xx, sort(ii, 0, n);
for (j = 0; j < m; j++)
jj[j] = j;
aa = yy, sort(jj, 0, m);
for (h = 0; h < k; h++)
hh[h] = h;
aa = ss, sort(hh, 0, k);
for (h = 0, j = 0; h < k; h++) {
while (j < m && yy[jj[j]] <= ss[hh[h]])
j++;
ss[hh[h]] = m - j;
}
aa = ww, sort(hh, 0, k);
n_ = 1;
while (n_ < m + 1)
n_ <<= 1;
lower = 0, upper = k + 1;
while (upper - lower > 1) {
int t = (lower + upper) / 2;
if (solve(xx, ii, n, ww, ss, hh, k, t))
upper = t;
else
lower = t;
}
return upper == k + 1 ? -1 : upper;
}
