Submission #139204

#TimeUsernameProblemLanguageResultExecution timeMemory
139204Mahmoud_AdelCake 3 (JOI19_cake3)C++14
5 / 100
8 ms1400 KiB
#include <bits/stdc++.h> #define f first #define s second using namespace std; typedef long long ll; const int N = 2e5+5; ll n, k, cn, ans = -1e18; ll root[N], lc[N*4], rc[N*4]; pair<ll, ll> tree[N*4]; vector<ll> comp; pair<ll, ll> p[N]; void merge(int node) { tree[node].f = tree[lc[node]].f+tree[rc[node]].f; tree[node].s = tree[lc[node]].s+tree[rc[node]].s; } void build(int node = 0, int l=0, int r=n-1) { if(l == r) { tree[node] = {1, comp[l]}; //cout << node << " " << tree[node].f << " " << tree[node].s << " | " << l << " " << r << endl; return ; } int mid = (l+r)>>1; lc[node] = ++cn, rc[node] = ++cn; build(lc[node], l, mid); build(rc[node], mid+1, r); merge(node); //cout << node << " " << tree[node].f << " " << tree[node].s << " | " << l << " " << r << endl; } void upd(int i, int node, int node2, int l=0, int r=n-1) { if(l == r) { tree[node] = {0, 0}; //cout << node << " " << tree[node].f << " " << tree[node].s << " | " << l << " " << r << endl; return ; } int mid = (l+r)>>1; if(i > mid) { rc[node] = ++cn; lc[node] = lc[node2]; upd(i, rc[node], rc[node2], mid+1, r); } else { rc[node] = rc[node2]; lc[node] = ++cn; upd(i, lc[node], lc[node2], l, mid); } merge(node); //cout << node << " " << tree[node].f << " " << tree[node].s << " | " << l << " " << r << endl; } bool cmp(pair<ll, ll> a, pair<ll, ll> b) { return a.s < b.s; } ll sum2(ll l, ll r) { vector<ll> vec; ll ret = 0; for(ll i=l; i<=r; i++) { vec.push_back(p[i].f); } sort(vec.rbegin(), vec.rend()); for(ll i=0; i<k; i++) ret += vec[i]; return ret; } ll sum(int node1, int node2, ll cnt) { ll cmt = tree[rc[node2]].f-tree[rc[node1]].f; //cout << node1 << " " << node2 << " | " << rc[node1] << " " << lc[node1] // << " | " << cmt << " " << cnt << " " << tree[node2].f-tree[node1].f << endl; //assert(tree[node2].f-tree[node1].f >= cnt); if(tree[node2].f-tree[node1].f == cnt) return tree[node2].s-tree[node1].s; if(!cnt) return 0; else if(cmt >= cnt) return sum(rc[node1], rc[node2], cnt); else return sum(rc[node1], rc[node2], cmt) + sum(lc[node1], lc[node2], cnt-cmt); } void solve(ll l, ll r, ll s, ll e) { if(l > r) return ; ll id = -1, m = -1e18; ll mid = (l+r)>>1; for(ll i=max(mid+k-1, (ll)s); i<=e; i++) { ll tmp; if(tree[root[mid]].f-tree[root[i+1]].f >= k) tmp = sum(root[i+1], root[mid], k); else tmp = sum2(mid, i); tmp -= (p[i].s-p[mid].s)*2LL; if(tmp > m) m = tmp, id = i; } solve(l, mid-1, s, id); solve(mid+1, r, id, e); ans = max(ans, m); } int main() { cin >> n >> k; for(int i=0; i<n; i++) cin >> p[i].f >> p[i].s, comp.push_back(p[i].f); sort(comp.begin(), comp.end()); sort(p, p+n, cmp); build(); for(int i=1; i<=n; i++) { int id = lower_bound(comp.begin(), comp.end(), p[i-1].f)-comp.begin(); root[i] = ++cn; upd(id, root[i], root[i-1]); } solve(0, n-k, 0, n-1); cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...