436E - Cardboard Box - CodeForces Solution

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e6 + 5;
int n , a[MAXN] , b[MAXN] , w , pre , len , lsh[MAXN] , ans[MAXN] , Cost[MAXN];
struct node{
	int a , b , id;
	friend bool operator<(node x , node y) {return (x.b == y.b ? x.a < y.a : x.b < y.b);}
}e[MAXN];
struct BIT{
	#define lowbit(x) ((x) & (-x))
	int bit[MAXN];
	void update(int k , int x) {
		for (int i = k ; i <= len ; i += lowbit(i)) bit[i] += x;
	}
	int Sum(int k) {
		int sum = 0;
		for (int i = k ; i ; i -= lowbit(i)) sum += bit[i];
		return sum;
	}
}F1 , F2;
struct Cos{
	int id , w;
	Cos(int _id , int _w) {id = _id , w = _w;}
	friend bool operator<(Cos x , Cos y) {return x.w > y.w;}
};
void print(int pos) {
	priority_queue<Cos> q;
	for (int i = 1 ; i <= pos ; i ++) q.push(Cos(e[i].id , e[i].b - e[i].a)) , ans[e[i].id] = 1;
	for (int i = pos + 1 ; i <= n ; i ++) q.push(Cos(e[i].id , e[i].a));
	int need = w - pos;
	while(need) {
		need --;
		ans[q.top().id] ++;
		q.pop();
	}
	cout << Cost[pos] << '\n';
	for (int i = 1 ; i <= n ; i ++) cout << ans[i];
}
signed main() {
	memset(Cost , 0x3f , sizeof(Cost));
	ios::sync_with_stdio(false);
	cin.tie(nullptr) , cout.tie(nullptr);
	cin >> n >> w;				
	int Minn = 1e16;			
	for (int i = 1 ; i <= n ; i ++) {
		cin >> e[i].a >> e[i].b;
		Minn = min(e[i].a , Minn);
		e[i].id = i;
		lsh[++ len] = e[i].a , lsh[++ len] = e[i].b - e[i].a;
	}
	if (w == 1) {
		cout << Minn << '\n';
		bool fout = 0;
		for (int i = 1 ; i <= n ; i ++) {
			if (e[i].a == Minn && !fout) cout << 1 , fout = 1;
			else cout << 0;
		}
		return 0;
	}
	sort(e + 1 , e + n + 1);
	sort(lsh + 1 , lsh + len + 1);
	len = unique(lsh + 1 , lsh + len + 1) - lsh - 1;
	for (int i = 1 ; i <= n ; i ++) {
		int upd = lower_bound(lsh + 1 , lsh + len + 1 , e[i].a) - lsh;
		F1.update(upd , 1) , F2.update(upd , e[i].a);
	}
	for (int i = 1 ; i <= n ; i ++) {
		int upd = lower_bound(lsh + 1 , lsh + len + 1 , e[i].a) - lsh;
		F1.update(upd , -1) , F2.update(upd , -e[i].a);
		upd = lower_bound(lsh + 1 , lsh + len + 1 , e[i].b - e[i].a) - lsh;
		F1.update(upd , 1) , F2.update(upd , e[i].b - e[i].a);
		pre += e[i].a;
		// --------------------------
		int need = w - i;
		int l = 1 , r = len;
		while(l < r) {
			int mid = l + r >> 1;
			if(F1.Sum(mid) >= need) r = mid;
			else l = mid + 1;
		}
		int rest = F1.Sum(l) - need;
		if (rest < 0) continue;
		int cost = F2.Sum(l) - lsh[l] * rest;
		Cost[i] = cost + pre;
	}
	int Min = 1e16;
	for (int i = 1 ; i <= n ; i ++) Min = min(Min , Cost[i]);
	for (int i = 1 ; i <= n ; i ++) {
		if (Min == Cost[i]) {
			print(i);
			break;
		}
	}
	return 0;
}