#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#define int long long
const ll mod=998244353,mxn=3*8e4+5,lg=30,inf=1e18,minf=-1e9,Mxn=100000;
struct solve{
priority_queue<int>l;
priority_queue<int,vector<int>,greater<int>>r;
int suml=0,sumr=0,med=inf;
void add(int val){
if(val>med)r.push(val),sumr+=val;
else l.push(val),suml+=val;
balance();
}
void balance(){
while(r.size()>l.size()+1){
l.push(r.top());
sumr-=r.top();
suml+=r.top();
r.pop();
}
while(l.size()>r.size()+1){
r.push(l.top());
suml-=l.top();
sumr+=l.top();
l.pop();
}
}
int qry(){
if(l.size()>r.size()){
med=l.top();
return ((l.top()*l.size())-suml)+(sumr-(l.top()*r.size()));
}
else {
med=r.top();
return (sumr-(r.top()*r.size()))+((r.top()*l.size())-suml);
}
}
void init(){
while(!l.empty())l.pop();
while(!r.empty())r.pop();
suml=0;
sumr=0;
med=0;
}
}t;
int k,n;
int pref[mxn+10];
void subk1(){
int ans=0;
vector<int>v;
pair<char,int>a,b;
for(int i=0;i<n;i++){
cin>>a.f>>a.s>>b.f>>b.s;
if(a.f==b.f)ans+=abs(a.s-b.s);
else v.pb(b.s),v.pb(a.s),ans++;
}
sort(all(v));
for(auto i:v)ans+=abs(v[v.size()/2]-i);
cout<<ans;
}
int32_t main(){
fastio
cin>>k>>n;
if(k==1){
subk1();
return 0;
}
int ans=0;
vector<pii>v;
pair<char,int>a,b;
t.init();
for(int i=0;i<n;i++){
cin>>a.f>>a.s>>b.f>>b.s;
if(a.f==b.f)ans+=abs(a.s-b.s);
else v.pb({min(a.s,b.s),max(a.s,b.s)}),ans++;
}
sort(all(v));
int add;
for(int i=0;i<v.size();i++){
t.add(v[i].f);
t.add(v[i].s);
pref[i]=t.qry();
add=pref[i];
}
t.init();
for(int i=v.size()-1;i>1;i--){
t.add(v[i].f);
t.add(v[i].s);
add=min(add,t.qry()+pref[i-1]);
}
cout<<ans+add;
}
Compilation message
bridge.cpp: In function 'int32_t main()':
bridge.cpp:106:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int i=0;i<v.size();i++){
| ~^~~~~~~~~
bridge.cpp:118:12: warning: 'add' may be used uninitialized in this function [-Wmaybe-uninitialized]
118 | cout<<ans+add;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
472 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 |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
464 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 |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
472 KB |
Output is correct |
11 |
Correct |
1 ms |
416 KB |
Output is correct |
12 |
Correct |
15 ms |
3288 KB |
Output is correct |
13 |
Correct |
35 ms |
4568 KB |
Output is correct |
14 |
Correct |
26 ms |
3796 KB |
Output is correct |
15 |
Correct |
19 ms |
2776 KB |
Output is correct |
16 |
Correct |
18 ms |
3856 KB |
Output is correct |
17 |
Correct |
22 ms |
4312 KB |
Output is correct |
18 |
Correct |
26 ms |
4056 KB |
Output is correct |
19 |
Correct |
30 ms |
4492 KB |
Output is correct |
20 |
Correct |
21 ms |
4056 KB |
Output is correct |
21 |
Correct |
29 ms |
4108 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 |
- |