Codeforces 436E Cardboard Box (看题解)

LL long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ull unsigned long long using namespace std; const int N = 3e5 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 + 7; const double eps = 1e-9; const double PI = acos(-1); #define lson l, mid, rt->ls #define rson mid + 1, r, rt->rs struct Node { Node() { ls = rs = NULL; sum = cnt = 0; } Node *ls, *rs; LL sum; int cnt; }; inline void pull(Node* rt) { rt->cnt = rt->ls->cnt + rt->rs->cnt; rt->sum = rt->ls->sum + rt->rs->sum; if(!rt->ls->cnt) delete rt->ls, rt->ls = NULL; if(!rt->rs->cnt) delete rt->rs, rt->rs = NULL; } inline void push(Node* rt) { if(!rt->ls) rt->ls = new Node(); if(!rt->rs) rt->rs = new Node(); } void update(int p, int c, int l, int r, Node* rt) { if(l == r) { rt->cnt += c; rt->sum += 1LL * p * c; return; } push(rt); int mid = l + r >> 1; if(p <= mid) update(p, c, lson); else update(p, c, rson); pull(rt); } LL query(int k, int l, int r, Node* rt) { if(!k) return 0; if(rt->cnt <= k) return rt->sum; if(l == r) return 1LL * k * l; push(rt); int mid = l + r >> 1; if(rt->ls->cnt >= k) return query(k, lson); else return query(rt->ls->cnt, lson) + query(k - rt->ls->cnt, rson); } int n, w, a[N], b[N], id[N], fin[N]; LL ans = INF; bool cmpa(int x, int y) { return a[x] < a[y]; } bool cmpb(int x, int y) { return b[x] < b[y]; } int main() { Node* Rt = new Node(); scanf("%d%d", &n, &w); for(int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]); for(int i = 1; i <= n; i++) id[i] = i; int where = -1; sort(id + 1, id + 1 + n, cmpa); if(w <= n) { LL ret = 0; for(int i = 1; i <= w; i++) ret += a[id[i]]; ans = min(ans, ret); where = 0; } sort(id + 1, id + 1 + n, cmpb); for(int i = 1; i <= n; i++) update(a[id[i]], 1, 1, inf, Rt); LL prefix = 0; LL ret = 0; for(int i = 1; i <= n; i++) { int x = id[i]; update(a[x], -1, 1, inf, Rt); ret = prefix + b[x]; int need = w - (i + 1); if(Rt->cnt >= need) { ret += query(need, 1, inf, Rt); if(ret < ans) { ans = ret; where = i; } } prefix += a[x]; update(b[x] - a[x], 1, 1, inf, Rt); } if(!where) { sort(id + 1, id + 1 + n, cmpa); for(int i = 1; i <= w; i++) fin[id[i]] = 1; } else { priority_queue<PII, vector<PII>, greater<PII> > que; fin[id[where]] = 2; w -= where + 1; for(int i = 1; i < where; i++) que.push(mk(b[id[i]] - a[id[i]], i)), fin[id[i]] = 1; for(int i = where + 1; i <= n; i++) que.push(mk(a[id[i]], i)); while(w--) { int who = que.top().se; que.pop(); if(who < where) fin[id[who]] = 2; else fin[id[who]] = 1; } } printf("%lld\n", ans); for(int i = 1; i <= n; i++) printf("%d", fin[i]); puts(""); return 0; } /* */

 

Codeforces 436E Cardboard Box (看题解)

标签：com   pre   for   unsigned   维护   lld   i++   put   col