This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200000;
const long long INF = 1LL << 60;
struct PersistentSegtree {
int cnt;
long long sum;
PersistentSegtree *lT, *rT;
PersistentSegtree() {
cnt = 0;
sum = 0LL;
lT = rT = NULL;
}
};
PersistentSegtree* build(int l, int r) {
int mid = (l + r) / 2;
PersistentSegtree* node = new PersistentSegtree();
if(l < r) {
node->lT = build(l, mid);
node->rT = build(mid + 1, r);
}
return node;
}
PersistentSegtree* update(int poz, long long val, int l, int r, PersistentSegtree* nod) {
if(poz < l || r < poz) return nod;
PersistentSegtree* newnode = new PersistentSegtree();
if(l == r) {
newnode->cnt = nod->cnt + 1;
newnode->sum = nod->sum + val;
} else {
int mid = (l + r) / 2;
newnode->lT = update(poz, val, l, mid, nod->lT);
newnode->rT = update(poz, val, mid + 1, r, nod->rT);
newnode->cnt = newnode->lT->cnt + newnode->rT->cnt;
newnode->sum = newnode->lT->sum + newnode->rT->sum;
}
return newnode;
}
long long query(int m, int l, int r, PersistentSegtree* minusTree, PersistentSegtree* plusTree) {
if(l == r) {
return plusTree->sum - minusTree->sum;
} else {
int leftCount = plusTree->lT->cnt - minusTree->lT->cnt, mid = (l + r) / 2;
if(leftCount < m)
return plusTree->lT->sum - minusTree->lT->sum +
query(m - leftCount, mid + 1, r, minusTree->rT, plusTree->rT);
else
return query(m, l, mid, minusTree->lT, plusTree->lT);
}
}
struct Slice {
int val, color, norm;
} slices[1+MAX_N];
bool colorSort(Slice a, Slice b) {
return a.color < b.color;
}
bool valueSort(Slice a, Slice b) {
return a.val < b.val;
}
long long solve(int l, int r, int cutL, int cutR, const int N, const int M, const vector<PersistentSegtree*> &versions) {
int mid = (l + r) / 2, cut = cutL;
long long rez = -INF;
for(int i = cutL; i <= cutR && i <= mid - M + 1; ++i) {
long long cost = query(M, 1, N, versions[i - 1], versions[mid]) - 2 * (slices[mid].color - slices[i].color);
if(cost > rez) {
rez = cost;
cut = i;
}
}
if(l < r) {
rez = max(rez, solve(l, mid - 1, cutL, cut, N, M, versions));
rez = max(rez, solve(mid + 1, r, cut, cutR, N, M, versions));
}
return rez;
}
int main() {
int N, M;
vector<PersistentSegtree*> versions;
scanf("%d%d", &N, &M);
for(int i = 1; i <= N; ++i)
scanf("%d%d", &slices[i].val, &slices[i].color);
sort(slices + 1, slices + 1 + N, valueSort);
for(int i = 1; i <= N; ++i)
slices[i].norm = N - i + 1;
sort(slices + 1, slices + 1 + N, colorSort);
versions.push_back(build(1, N));
for(int i = 1; i <= N; ++i)
versions.push_back(update(slices[i].norm, slices[i].val, 1, N, versions.back()));
printf("%lld", solve(1, N, 1, N, N, M, versions));
return 0;
}
Compilation message (stderr)
cake3.cpp: In function 'int main()':
cake3.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
cake3.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &slices[i].val, &slices[i].color);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |