이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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(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;
}
컴파일 시 표준 에러 (stderr) 메시지
bridge.cpp: In function 'int main()':
bridge.cpp:62: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... |