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;
struct ab {
int a, b;
};
struct event {
int type, val, t;
};
const int MAX_N = 2e5;
const long long INF = 1e18;
const int MAX_EVENTS = 2 * MAX_N;
int m;
int timee = 0;
int nrEv = 0;
long long sumA = 0;
long long ans = -INF;
ab v[MAX_N + 1];
event events[MAX_EVENTS];
multiset <int> s;
void solve( int ll, int lr, int rl, int rr ) {
if ( ll > lr || rl > rr || rr - ll + 1 < m )
return;
int l = (ll + lr) / 2;
long long answer = -INF;
int bestR = rr;
int t = timee;
for ( int i = l; i <= lr && i < rl; i++ ) {
s.insert( v[i].a );
sumA += v[i].a;
events[nrEv++] = { 1, v[i].a, ++timee };
if ( s.size() > m ) {
sumA -= *s.begin();
events[nrEv++] = { -1, *s.begin(), ++timee };
s.erase( s.begin() );
}
}
for ( int r = max( l, rl ); r <= rr; r++ ) {
s.insert( v[r].a );
sumA += v[r].a;
events[nrEv++] = { 1, v[r].a, ++timee };
if ( s.size() > m ) {
sumA -= *s.begin();
events[nrEv++] = { -1, *s.begin(), ++timee };
s.erase( s.begin() );
}
if ( s.size() >= m ) {
if ( sumA - 2 * (v[r].b - v[l].b) > answer ) {
answer = sumA - 2 * (v[r].b - v[l].b);
bestR = r;
}
}
}
while ( nrEv > 0 && events[nrEv - 1].t > t ) {
int x = events[nrEv - 1].val;
if ( events[nrEv - 1].type == 1 ) {
s.erase( s.find( x ) );
sumA -= x;
} else {
s.insert( x );
sumA += x;
}
nrEv--;
}
for ( int i = min( rl - 1, lr ); i >= l; i-- ) {
s.insert( v[i].a );
sumA += v[i].a;
events[nrEv++] = { 1, v[i].a, ++timee };
if ( s.size() > m ) {
sumA -= *s.begin();
events[nrEv++] = { -1, *s.begin(), ++timee };
s.erase( s.begin() );
}
}
solve( ll, l - 1, rl, bestR );
while ( nrEv > 0 && events[nrEv - 1].t > t ) {
int x = events[nrEv - 1].val;
if ( events[nrEv - 1].type == 1 ) {
s.erase( s.find( x ) );
sumA -= x;
} else {
s.insert( x );
sumA += x;
}
nrEv--;
}
for ( int i = max( rl, lr + 1 ); i < bestR; i++ ) {
s.insert( v[i].a );
sumA += v[i].a;
events[nrEv++] = { 1, v[i].a, ++timee };
if ( s.size() > m ) {
sumA -= *s.begin();
events[nrEv++] = { -1, *s.begin(), ++timee };
s.erase( s.begin() );
}
}
solve( l + 1, lr, bestR, rr );
while ( nrEv > 0 && events[nrEv - 1].t > t ) {
int x = events[nrEv - 1].val;
if ( events[nrEv - 1].type == 1 ) {
s.erase( s.find( x ) );
sumA -= x;
} else {
s.insert( x );
sumA += x;
}
nrEv--;
}
ans = max( ans, answer );
}
int main() {
int n;
cin.tie( NULL );
ios_base::sync_with_stdio( false );
cin >> n >> m;
for ( int i = 1; i <= n; i++ )
cin >> v[i].a >> v[i].b;
sort( v + 1, v + 1 + n, []( ab x, ab y ) {
return x.b < y.b;
} );
solve( 1, n, 1, n );
cout << ans;
return 0;
}
Compilation message (stderr)
cake3.cpp: In function 'void solve(int, int, int, int)':
cake3.cpp:40:23: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
40 | if ( s.size() > m ) {
| ~~~~~~~~~^~~
cake3.cpp:51:23: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
51 | if ( s.size() > m ) {
| ~~~~~~~~~^~~
cake3.cpp:57:23: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
57 | if ( s.size() >= m ) {
| ~~~~~~~~~^~~~
cake3.cpp:80:23: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | if ( s.size() > m ) {
| ~~~~~~~~~^~~
cake3.cpp:103:23: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
103 | if ( s.size() > m ) {
| ~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |