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>
#define int long long
#define iris 998244353
#define pii pair<int,int>
using namespace std;
vector<int> ouo;
vector<pii> arr;
priority_queue<int> ll;
priority_queue<int,vector<int>,greater<int> > rr;
int lsum,rsum;
int ans[100010];
bool cmp(pii a,pii b)
{
return a.first+a.second<b.first+b.second;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
char x,y;
int k,n,i,a,b,sum,sagiri,l,r,m;
sum=0;
cin>>k>>n;
for(i=0;i<n;i++)
{
cin>>x>>a>>y>>b;
if(a>b)
{
swap(a,b);
}
if(x==y)
{
sum+=abs(a-b);
}
else
{
sum++;
if(k==1)
{
ouo.emplace_back(a);
ouo.emplace_back(b);
}
else
{
arr.emplace_back(make_pair(a,b));
}
}
}
if(k==1)
{
sort(ouo.begin(), ouo.end());
m=ouo[ouo.size()/2];
for(int aoi:ouo)
{
sum+=abs(aoi-m);
}
cout<<sum<<'\n';
}
else
{
sort(arr.begin(), arr.end(), cmp);
lsum=rsum=0;
for(i=0;i<arr.size();i++)
{
l=arr[i].first;
r=arr[i].second;
ll.push(l);
ll.push(r);
lsum+=l+r;
while(!ll.empty() && !rr.empty() && ll.top()>rr.top())
{
rsum+=ll.top();
lsum-=ll.top();
rr.push(ll.top());
ll.pop();
}
while(ll.size()+1 < rr.size())
{
lsum+=rr.top();
rsum-=rr.top();
ll.push(rr.top());
rr.pop();
}
while(ll.size() > rr.size())
{
rsum+=ll.top();
lsum-=ll.top();
rr.push(ll.top());
ll.pop();
}
m=ll.top();
ans[i+1]=m*ll.size()-lsum+rsum-m*rr.size();
}
while(!ll.empty())
ll.pop();
while(!rr.empty())
rr.pop();
sagiri=1e18;
lsum=rsum=0;
for(i=arr.size()-1;i>=0;i--)
{
l=arr[i].first;
r=arr[i].second;
ll.push(l);
ll.push(r);
lsum+=l+r;
while(!ll.empty() && !rr.empty() && ll.top()>rr.top())
{
rsum+=ll.top();
lsum-=ll.top();
rr.push(ll.top());
ll.pop();
}
while(ll.size()+1 < rr.size())
{
lsum+=rr.top();
rsum-=rr.top();
ll.push(rr.top());
rr.pop();
}
while(ll.size() > rr.size())
{
rsum+=ll.top();
lsum-=ll.top();
rr.push(ll.top());
ll.pop();
}
m=ll.top();
ans[i]+=m*ll.size()-lsum+rsum-m*rr.size();
sagiri=min(sagiri, ans[i]);
}
cout<<sagiri+sum<<'\n';
}
return 0;
}
Compilation message (stderr)
bridge.cpp: In function 'int main()':
bridge.cpp:66:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<arr.size();i++)
~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |