#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// PUT IT BEFORE THE INCLUDE
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18 + 7;
struct ONLINE_MEDIAN{
long long sum1 = 0 , sum2 = 0;
int sz = 0;
multiset < int > s1,s2;
inline void insert(int x){
if(s1.size() == 0 or *(--s1.end()) >= x){
sum1 += x;
s1.insert(x);
}
else{
sum2 += x;
s2.insert(x);
}
sz++;
if(s1.size() > ((sz+1)/2)){
sum2 += *(--s1.end());
s2.insert(*(--s1.end())),
sum1 -= *(--s1.end());
s1.erase(--s1.end());
}
if(s1.size() < ((sz+1)/2)){
sum1 += *(s2.begin());
s1.insert(*s2.begin());
sum2 -= *(s2.begin());
s2.erase(s2.begin());
}
}
inline void erase(int x){
if(s1.count(x)){
sum1 -= x;
s1.erase(s1.find(x));
}
else {
sum2 -= x;
s2.erase(s2.find(x));
}
sz--;
if(s1.size() > ((sz+1)/2)){
sum2 += *(--s1.end());
s2.insert(*(--s1.end())),
sum1 -= *(--s1.end());
s1.erase(--s1.end());
}
if(s1.size() < ((sz+1)/2)){
sum1 += *(s2.begin());
s1.insert(*s2.begin());
sum2 -= *(s2.begin());
s2.erase(s2.begin());
}
}
inline int get_median(){
if(s1.empty())return 0;
return *(--s1.end());
}
inline long long get_ans(){
int medi = get_median();
return (1ll * medi * s1.size() - sum1) + (sum2 - 1ll * medi * s2.size());
}
inline 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;
long long 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]);
}
long long ans1 = inf;
if(k == 1){
ans1 = 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 == inf ? 0ll : ans1) + v2.size() << '\n';
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
}
Compilation message
bridge.cpp: In member function 'void ONLINE_MEDIAN::insert(int)':
bridge.cpp:21:16: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
21 | if(s1.size() > ((sz+1)/2)){
| ~~~~~~~~~~^~~~~~~~~~~~
bridge.cpp:27:16: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
27 | if(s1.size() < ((sz+1)/2)){
| ~~~~~~~~~~^~~~~~~~~~~~
bridge.cpp: In member function 'void ONLINE_MEDIAN::erase(int)':
bridge.cpp:44:16: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
44 | if(s1.size() > ((sz+1)/2)){
| ~~~~~~~~~~^~~~~~~~~~~~
bridge.cpp:50:16: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
50 | if(s1.size() < ((sz+1)/2)){
| ~~~~~~~~~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 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 |
504 KB |
Output is correct |
6 |
Correct |
1 ms |
376 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 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 |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
49 ms |
11556 KB |
Output is correct |
13 |
Correct |
98 ms |
12356 KB |
Output is correct |
14 |
Correct |
76 ms |
10688 KB |
Output is correct |
15 |
Correct |
54 ms |
7640 KB |
Output is correct |
16 |
Correct |
48 ms |
11796 KB |
Output is correct |
17 |
Correct |
53 ms |
12396 KB |
Output is correct |
18 |
Correct |
52 ms |
12244 KB |
Output is correct |
19 |
Correct |
70 ms |
12508 KB |
Output is correct |
20 |
Correct |
58 ms |
12288 KB |
Output is correct |
21 |
Correct |
56 ms |
12200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
4 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
3 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
472 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
3 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
456 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
4 ms |
348 KB |
Output is correct |
14 |
Correct |
2 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
3 ms |
580 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
3 ms |
464 KB |
Output is correct |
24 |
Correct |
1 ms |
344 KB |
Output is correct |
25 |
Execution timed out |
2058 ms |
11724 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |