#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<int> taskai;
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;
}
///-----------------------------------------
priority_queue<int> dideli2, mazi2;
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(dideli2.size()==0)
{
dideli2.push(-x);
mazi2.push(y);
suma_dideliu+=x;
suma_mazu+=y;
}
else
{
if(x>-dideli2.top() || x>mazi2.top())
{
suma_dideliu+=x;
suma_mazu+=y;
dideli2.push(-x);
mazi2.push(y);
}
///prielaida, kad abu i didziausius niekada neis
else
{
suma_mazu-=mazi2.top();
suma_dideliu+=mazi2.top();
dideli2.push(-mazi2.top());
mazi2.pop();
suma_mazu+=x+y;
mazi2.push(x);
mazi2.push(y);
}
}
//int mediana=-dideli.top();
ats[i-1][1]=suma_dideliu-suma_mazu;
//cout << ats[i-1][1] << endl;
/*priority_queue<int> isvedimui=dideli2;
while(!isvedimui.empty())
{
cout << -isvedimui.top() << ' ';
isvedimui.pop();
}
cout << endl;
isvedimui=mazi2;
while(!isvedimui.empty())
{
cout << isvedimui.top() << ' ';
isvedimui.pop();
}
cout << endl << 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
bridge.cpp: In function 'int main()':
bridge.cpp:40: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]
40 | for(int i=0; i<v.size(); i++)
| ~^~~~~~~~~
bridge.cpp:54: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]
54 | for(int i=0; i<vidurio_taskai.size()-1; i++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:150: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]
150 | for(int i=0; i<v.size()-1; i++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
0 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 |
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 |
1 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 |
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 |
12 ms |
2824 KB |
Output is correct |
| 13 |
Correct |
24 ms |
2880 KB |
Output is correct |
| 14 |
Correct |
18 ms |
2512 KB |
Output is correct |
| 15 |
Correct |
19 ms |
1908 KB |
Output is correct |
| 16 |
Correct |
15 ms |
3004 KB |
Output is correct |
| 17 |
Correct |
21 ms |
2756 KB |
Output is correct |
| 18 |
Correct |
20 ms |
2820 KB |
Output is correct |
| 19 |
Correct |
23 ms |
2756 KB |
Output is correct |
| 20 |
Correct |
15 ms |
2852 KB |
Output is correct |
| 21 |
Correct |
21 ms |
2756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
103 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
96 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
118 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
