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>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int k, n;
cin >> k >> n;
vector<pair<int, int>> v;
vector<int> sarasas;
vector<pair<int, int>> vidurio_taskai;
set<int> s;
long long priedas=0;
for(int i=0; i<n; i++)
{
char cg, cd;
int ig, id;
cin >> cg >> ig >> cd >> id;
if(cg!=cd)
{
priedas++;
v.push_back({ig, id});
vidurio_taskai.push_back({(ig+id)/2, v.size()-1});
sarasas.push_back(ig);
sarasas.push_back(id);
}
else
{
priedas+=abs(ig-id);
}
}
if(k==1)
{
sort(sarasas.begin(), sarasas.end());
int tiltas=sarasas.size()/2;
long long sum=priedas;
for(int i=0; i<v.size(); i++)
{
sum+=abs(v[i].first-sarasas[tiltas])+abs(v[i].second-sarasas[tiltas]);
}
cout << sum;
}
else
{
sort(sarasas.begin(), sarasas.end());
sort(vidurio_taskai.begin(), vidurio_taskai.end());
priority_queue<int> dideli, mazi;
long long suma_dideliu=0, suma_mazu=0;
long long ats[vidurio_taskai.size()-1][2];
for(int i=0; i<vidurio_taskai.size()-1; i++)
{
//cout << "Paimta " << i+1 << " poru: ";
int x=v[vidurio_taskai[i].second].first;
int y=v[vidurio_taskai[i].second].second;
if(x<y) swap(x, y);
if(dideli.size()==0)
{
dideli.push(-x);
mazi.push(y);
suma_dideliu+=x;
suma_mazu+=y;
}
else
{
if(y>-dideli.top())
{
suma_dideliu-=-dideli.top();
suma_mazu+=-dideli.top();
mazi.push(-dideli.top());
dideli.pop();
suma_dideliu+=x+y;
dideli.push(-x);
dideli.push(-y);
}
///prielaida, kad abu i maziausius niekada neis
else
{
suma_dideliu+=x;
suma_mazu+=y;
dideli.push(-x);
mazi.push(y);
}
}
//int mediana=-dideli.top();
ats[i][0]=suma_dideliu-suma_mazu;
//cout << ats[i][0] << endl;
}
///-----------------------------------------
while(!mazi.empty()) mazi.pop();
while(!dideli.empty()) dideli.pop();
suma_dideliu=0, suma_mazu=0;
for(int i=vidurio_taskai.size()-1; i>0; i--)
{
//cout << "Paimta " << vidurio_taskai.size()-i << " poru nuo galo: ";
int x=v[vidurio_taskai[i].second].first;
int y=v[vidurio_taskai[i].second].second;
if(x<y) swap(x, y);
//cout << x << ' ' << y << " ";
if(dideli.size()==0)
{
dideli.push(-x);
mazi.push(y);
suma_dideliu+=x;
suma_mazu+=y;
}
else
{
if(x>-dideli.top() || x>mazi.top())
{
suma_dideliu+=x;
suma_mazu+=y;
dideli.push(-x);
mazi.push(y);
}
///prielaida, kad abu i didziausius niekada neis
else
{
suma_mazu-=mazi.top();
suma_dideliu+=mazi.top();
dideli.push(-mazi.top());
mazi.pop();
suma_mazu+=x+y;
mazi.push(x);
mazi.push(y);
}
}
//int mediana=-dideli.top();
ats[i-1][1]=suma_dideliu-suma_mazu;
//cout << ats[i-1][1] << endl;
}
long long atsakymas=LONG_MAX;
for(int i=0; i<v.size()-1; i++)
{
atsakymas=min(atsakymas, ats[i][0]+ats[i][1]);
}
atsakymas+=priedas;
cout << atsakymas;
}
return 0;
}
Compilation message (stderr)
bridge.cpp: In function 'int main()':
bridge.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0; i<v.size(); i++)
| ~^~~~~~~~~
bridge.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i=0; i<vidurio_taskai.size()-1; i++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:136:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int i=0; i<v.size()-1; 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... |