#include <bits/stdc++.h>
using namespace std;
#define int long long
struct ONLINE_MEDIAN{
int sum1 = 0 , sum2 = 0 , sz = 0;
multiset < int > s1,s2;
void insert(int x){
sum2 += x;
s2.insert(x);
sz++;
while(s1.size() < ((sz+1)/2)){
sum1 += *s2.begin();
s1.insert(*s2.begin());
sum2 -= *s2.begin();
s2.erase(s2.begin());
}
while(s2.size() and *(--s1.end()) > *(s2.begin())){
sum2 += *(--s1.end());
s2.insert(*(--s1.end()));
sum1 -= *(--s1.end());
s1.erase(--s1.end());
sum1 += *s2.begin();
s1.insert(*s2.begin()),
sum2 -= *s2.begin();
s2.erase(s2.begin());
}
}
void erase(int x){
if(s1.count(x)){
sum1 -= x;
s1.erase(s1.find(x));
}
else {
sum2 -= x;
s2.erase(s2.find(x));
}
sz--;
while(s1.size() > ((sz+1)/2)){
sum2 += *(--s1.end());
s2.insert(*(--s1.end())),
sum1 -= *(--s1.end());
s1.erase(--s1.end());
}
while(s1.size() < ((sz+1)/2)){
sum1 += *(s2.begin());
s1.insert(*s2.begin());
sum2 -= *(s2.begin());
s2.erase(s2.begin());
}
while(s2.size() and *(--s1.end()) > *(s2.begin())){
sum2 += *(--s1.end());
s2.insert(*(--s1.end()));
sum1 -= *(--s1.end());
s1.erase(--s1.end());
sum1 += *s2.begin();
s1.insert(*s2.begin()),
sum2 -= *s2.begin();
s2.erase(s2.begin());
}
}
int get_median(){
if(s1.empty())return 0;
return *(--s1.end());
}
int get_ans(){
int medi = get_median();
return (medi * s1.size() - sum1) + (sum2 - medi * s2.size());
}
void debug(){
cout << "set : ";
for(auto itr : s1)cout << itr << " ";
cout << "|";
for(auto itr : s2)cout << itr << " ";
}
};
bool cmp(array < int , 3 > const& a , array < int , 3 > const& b){
return a[0] < b[0];
}
void solve(){
int k,n,ans0 = 0;
cin >> k >> n;
vector < array < int , 3 > > v2;
for(int i = 0;i<n;i++){
char c1,c2;
int p1,p2;
cin >> c1 >> p1 >> c2 >> p2;
if(c1 == c2){
ans0 += abs(p1 - p2);
}
else{
v2.push_back({p1 + p2 , p1 , p2});
}
}
sort(v2.begin() , v2.end() , cmp);
ONLINE_MEDIAN med1 , med2;
for(auto itr : v2){
med2.insert(itr[1]);
med2.insert(itr[2]);
}
int ans1 = 1e18 + 7;
if(k == 1){
ans1 = med1.get_ans() + med2.get_ans();
}
else{
for(auto itr : v2){
med2.erase(itr[1]);
med2.erase(itr[2]);
med1.insert(itr[1]);
med1.insert(itr[2]);
ans1 = min(ans1 , med1.get_ans() + med2.get_ans());
}
}
cout << ans0 + ans1 + v2.size() << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
}
Compilation message
bridge.cpp: In member function 'void ONLINE_MEDIAN::insert(long long int)':
bridge.cpp:11:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
11 | while(s1.size() < ((sz+1)/2)){
| ~~~~~~~~~~^~~~~~~~~~~~
bridge.cpp: In member function 'void ONLINE_MEDIAN::erase(long long int)':
bridge.cpp:38:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
38 | while(s1.size() > ((sz+1)/2)){
| ~~~~~~~~~~^~~~~~~~~~~~
bridge.cpp:44:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
44 | while(s1.size() < ((sz+1)/2)){
| ~~~~~~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
424 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
548 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
528 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
536 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
59 ms |
12936 KB |
Output is correct |
13 |
Correct |
93 ms |
14268 KB |
Output is correct |
14 |
Correct |
100 ms |
12256 KB |
Output is correct |
15 |
Correct |
51 ms |
8708 KB |
Output is correct |
16 |
Correct |
64 ms |
13760 KB |
Output is correct |
17 |
Correct |
61 ms |
14784 KB |
Output is correct |
18 |
Correct |
70 ms |
14088 KB |
Output is correct |
19 |
Correct |
79 ms |
14368 KB |
Output is correct |
20 |
Correct |
62 ms |
14268 KB |
Output is correct |
21 |
Correct |
64 ms |
14236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |