关于梦熊 OJ 测试赛F题

#include <bits/stdc++.h>
#define int ll
using namespace std;
typedef __int128 ll;
const int N = 1e6 + 5;
ll a[N], b[N], t[N];
ll ans, cnt, n, m, h, lst, nown, nowm, del, D;
map <ll, vector <ll> > c;
struct BIT {
    ll t[N];
    ll lowbit(ll x) {return x & (-x);}
    void add(ll x, ll y) {for (ll i = x; i <= n; i += lowbit(i)) t[i] += y;}
    int sum(ll r) {
        ll res = 0;
        for (ll i = r; i; i -= lowbit(i)) res += t[i];
        return res;
    }
    ll sum(ll l, ll r) {return sum(r) - sum(l - 1);}
} T;
ll get(ll L, ll v) {
	if (!v) return 0;
	ll l = L, r = n, mid, ret;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (T.sum(L, mid) <= v) ret = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ret;
}
inline void read(ll &x){x=0;char c=getchar();bool p=1;
	for(;'0'>c||c>'9';c=getchar()) if(c=='-') p=0;
	for(;'0'<=c&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+(c^48);p?:x=-x;
}
void write(ll num) {
	if (num > 9) write(num / 10);
	putchar(num % 10 + '0');
}
signed main() {
	freopen("in.txt", "r", stdin);
	read(n), read(m), read(h);
	for (int i = 1; i <= n; i ++) read(a[i]);
	for (int i = 1; i <= n; i ++) read(b[i]);
	for (int i = 1; i <= n; i ++) {
		if (a[i] > h) t[i] = 0;
		else t[i] = (h - a[i]) / b[i], t[i] ++;
		c[t[i]].push_back(i);
		T.add(i, 1);
	}
	sort(t + 1, t + n + 1);
	cnt = unique(t + 1, t + n + 1) - t - 1;
	nown = n, nowm = m;
	for (int i = 1; i <= cnt; i ++) {
//		cerr << lst << endl;
		if (lst != 0) {
			del = T.sum(lst + 1, n);
			if (del > t[i] - t[i - 1]) {
				ans += t[i] - t[i - 1];
				lst = get(lst + 1, t[i] - t[i - 1]);
				nown -= c[t[i]].size();
				for (auto f : c[t[i]]) T.add(f, -1);
				continue;
			}
			ans += del;
		} else del = 0;
		if (nown <= 0) break;
		if (nowm <= 0) break;
		D = t[i] - t[i - 1] - del;
		if (D / nown <= nowm) {
			ans += D;
			nowm -= D / nown;
			if (D % nown) nowm --;
			lst = get(1, D % nown);
			nown -= c[t[i]].size();
			for (auto f : c[t[i]]) T.add(f, -1);
		} else { 
			ans += nown * nowm;
			break;
		}
//		cerr << ans << endl;
	}
	write(ans);
	return 0;
}