#include <bits/stdc++.h>
using namespace std;
struct gyventojas
{
char p;
double s;
char q;
double t;
};
const int maxn = 100000;
const long long daug = 1000000000000000;
int k, n, kiek;
gyventojas M[maxn];
vector <int> reikalingi;
vector <int> nereikalingi;
vector <int> medianai;
vector <int> unikalus;
set <int> buvo;
long long skaiciuok_keliu_suma(int tiltas1, int tiltas2)
{
long long ats = 0;
if(kiek>0)
{
if(k == 1)
{
for(int i = 0; i<reikalingi.size(); i++)
{
int j = reikalingi[i];
ats += abs(M[j].s - tiltas1) + abs(M[j].t - tiltas1);
}
}
else
{
for(int f = 0; f<reikalingi.size(); f++)
{
int x = reikalingi[f];
int a1 = abs(M[x].s - tiltas1) + abs(M[x].t - tiltas1);
int a2 = abs(M[x].s - tiltas2) + abs(M[x].t - tiltas2);
ats += min(a1, a2);
}
}
}
for(int i = 0; i<nereikalingi.size(); i++)
{
int j = nereikalingi[i];
ats += abs(M[j].s - M[j].t);
}
return ats + reikalingi.size();
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> k >> n;
for(int i = 0; i<n; i++)
{
cin >> M[i].p >> M[i].s >> M[i].q >> M[i].t;
if(M[i].p != M[i].q)
{
reikalingi.push_back(i);
medianai.push_back(M[i].s);
medianai.push_back(M[i].t);
if(buvo.find(M[i].s) == buvo.end())
{
buvo.insert(M[i].s);
unikalus.push_back(M[i].s);
}
if(buvo.find(M[i].t) == buvo.end())
{
buvo.insert(M[i].t);
unikalus.push_back(M[i].t);
}
}
else nereikalingi.push_back(i);
}
sort(medianai.begin(), medianai.end());
kiek = reikalingi.size();
if(k==1)
{
if(kiek > 0) cout << skaiciuok_keliu_suma(medianai[medianai.size()/2], -1);
else cout << skaiciuok_keliu_suma(-1, -1);
}
else
{
pair<double, int> st2[n];
for(int i = 0; i<n; i++)
{
st2[i] = {(M[i].s+M[i].t)/2, i};
}
sort(st2, st2+n);
long long sumos_kaire[n-1];
long long sumos_desine[n-1];
///i kaire puse
priority_queue <int> q1;
priority_queue <int> q2;
long long s1 = 0;
long long s2 = 0;
int s = M[st2[0].second].s;
int t = M[st2[0].second].t;
if(s>t) swap(s, t);
q1.push(s);
q2.push(-t);
s1 += s;
s2 += t;
sumos_kaire[0] = -s1+s2;
//cout << sumos_kaire[0] << ' ';
//cout << ']' << s1 << ' ' << s2 << endl;
for(int i = 1; i<n-1; i++)
{
s = M[st2[i].second].s;
t = M[st2[i].second].t;
if(s>t) swap(s,t);
if(s <= -q2.top() && t >= q1.top())
{
//cout << '!';
q1.push(s);
q2.push(-t);
s1 += s;
s2 += t;
//cout << s1 << ' ' << s2 << endl;
}
else if(t < q1.top())
{
//cout << '?';
q2.push(-q1.top());
s2 += q1.top();
s1 -= q1.top();
q1.pop();
q1.push(s);
q1.push(t);
s1+= t+s;
}
else if(s > -q2.top())
{
//cout << '/';
q1.push(-q2.top());
s1 += -q2.top();
s2 -= -q2.top();
q2.pop();
q2.push(s);
q2.push(t);
s2+= t+s;
}
sumos_kaire[i] = -s1+s2;
//cout << sumos_kaire[i] << ' ';
}
/// desine puse
while(!q1.empty())q1.pop();
while(!q2.empty())q2.pop();
s1 = 0;
s2 = 0;
s = M[st2[n-1].second].s;
t = M[st2[n-1].second].t;
//cout << "!!!!!!" << st2[n-1].first << endl;
if(s>t) swap(s, t);
q1.push(s);
q2.push(-t);
s1 += s;
s2 += t;
sumos_desine[n-2] = -s1+s2;
//cout << sumos_desine[n-2] << ' ';
//cout << ']' << s1 << ' ' << s2 << endl;
for(int i = n-2; i>=1; i--)
{
//cout << "!!!!!!" << st2[i].first << endl;
s = M[st2[i].second].s;
t = M[st2[i].second].t;
if(s>t) swap(s,t);
if(s <= -q2.top() && t >= q1.top())
{
//cout << '!';
q1.push(s);
q2.push(-t);
s1 += s;
s2 += t;
//cout << s1 << ' ' << s2 << endl;
}
else if(t < q1.top())
{
//cout << '?';
q2.push(-q1.top());
s2 += q1.top();
s1 -= q1.top();
q1.pop();
q1.push(s);
q1.push(t);
s1+= t+s;
}
else if(s > -q2.top())
{
//cout << '/';
q1.push(-q2.top());
s1 += -q2.top();
s2 -= -q2.top();
q2.pop();
q2.push(s);
q2.push(t);
s2+= t+s;
}
sumos_desine[i-1] = -s1+s2;
//cout << sumos_desine[i-1] << ' ';
}
long long galats = daug;
for(int i = 0; i<n-1; i++)
{
galats = min(galats, sumos_kaire[i] + sumos_desine[i]);
}
cout << galats + reikalingi.size();
}
return 0;
}
/*
2 4
A 1 B 6
A 5 B 3
A 8 B 7
A 10 B 10
2 2
A 10 B 5
A 1 B 1
2 3
A 10 B 5
A 6 B 8
A 1 B 1
2 4
A 10 B 5
A 6 B 8
A 3 B 4
A 1 B 1
*/
Compilation message
bridge.cpp: In function 'long long int skaiciuok_keliu_suma(int, int)':
bridge.cpp:32:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int i = 0; i<reikalingi.size(); i++)
| ~^~~~~~~~~~~~~~~~~~
bridge.cpp:40:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int f = 0; f<reikalingi.size(); f++)
| ~^~~~~~~~~~~~~~~~~~
bridge.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i = 0; i<nereikalingi.size(); i++)
| ~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
1 ms |
604 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
1 ms |
604 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
25 ms |
4772 KB |
Output is correct |
| 13 |
Correct |
102 ms |
14852 KB |
Output is correct |
| 14 |
Correct |
45 ms |
4912 KB |
Output is correct |
| 15 |
Correct |
53 ms |
9148 KB |
Output is correct |
| 16 |
Correct |
24 ms |
4812 KB |
Output is correct |
| 17 |
Correct |
88 ms |
14852 KB |
Output is correct |
| 18 |
Correct |
75 ms |
14768 KB |
Output is correct |
| 19 |
Correct |
81 ms |
14392 KB |
Output is correct |
| 20 |
Correct |
26 ms |
4812 KB |
Output is correct |
| 21 |
Correct |
70 ms |
14768 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 |
- |
