#include <bits/stdc++.h>
using namespace std;
long long k,n,num,other;
pair<long long,long long> p[100001];
bool cmp(pair<long long,long long> p1,pair<long long,long long> p2)
{
return p1.first+p1.second<p2.first+p2.second;
}
void read()
{
cin>>k>>n;
for(long long i=1;i<=n;i++)
{
char c1,c2;
long long x,y;
cin>>c1>>x>>c2>>y;
if(c1==c2)other+=abs(x-y);
else
{
num++;
p[num]={min(x,y),max(x,y)};
}
}
sort(p+1,p+num+1,cmp);
if(num==0)
{
cout<<other<<endl;
exit(0);
}
}
void solve1()
{
vector<long long> v;
for(long long i=1;i<=num;i++)
{
v.push_back(p[i].first);
v.push_back(p[i].second);
}
sort(v.begin(),v.end());
long long x=v[v.size()/2];
long long ans=other+num;
for(long long i=0;i<v.size();i++)
{
ans+=abs(v[i]-x);
}
cout<<ans<<endl;
}
long long l[100001],r[100001];
void solve2()
{
long long ans=1e18;
if(num==1)
{
cout<<other+1+p[1].second-p[1].first<<endl;
exit(0);
}
priority_queue<long long> q1,q2;
q1.push(p[1].first);
q2.push(-p[1].second);
l[1]=p[1].second-p[1].first;
for(long long i=2;i<=num;i++)
{
l[i]=l[i-1];
if(p[i].first<=q1.top())
{
l[i]+=q1.top()-p[i].first;
q1.push(p[i].first);
}
else
{
q2.push(-p[i].first);
q1.push(-q2.top());
q2.pop();
l[i]+=p[i].first-q1.top();
}
if(p[i].second<q1.top())
{
q1.push(p[i].second);
l[i]+=q1.top()-p[i].second;
q2.push(-q1.top());
q1.pop();
}
else
{
l[i]+=p[i].second-q1.top();
q2.push(-p[i].second);
}
//cout<<i<<" "<<l[i]<<" "<<q1.top()<<" "<<p[i].second<<endl;
}
while(q1.size())q1.pop();
while(q2.size())q2.pop();
q1.push(p[num].first);
q2.push(-p[num].second);
r[num]=p[num].second-p[num].first;
for(long long i=num-1;i>=1;i--)
{
r[i]=r[i+1];
if(p[i].first<=q1.top())
{
r[i]+=q1.top()-p[i].first;
q1.push(p[i].first);
}
else
{
q2.push(-p[i].first);
q1.push(-q2.top());
q2.pop();
r[i]+=p[i].first-q1.top();
}
if(p[i].second<q1.top())
{
q1.push(p[i].second);
r[i]+=q1.top()-p[i].second;
q2.push(-q1.top());
q1.pop();
}
else
{
r[i]+=p[i].second-q1.top();
q2.push(-p[i].second);
}
//cout<<i+1<<" "<<r[i+1]<<endl;
}
for(long long i=1;i<num;i++)
ans=min(ans,l[i]+r[i+1]+other+num);
cout<<ans<<endl;
}
int main()
{
read();
if(k==1)solve1();
else solve2();
return 0;
}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
1 3
A 1 B 1
A 5 B 5
A 6 B 6
*/
Compilation message
bridge.cpp: In function 'void solve1()':
bridge.cpp:53:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(long long i=0;i<v.size();i++)
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
2384 KB |
Output is correct |
4 |
Correct |
2 ms |
2384 KB |
Output is correct |
5 |
Correct |
2 ms |
2556 KB |
Output is correct |
6 |
Correct |
2 ms |
2384 KB |
Output is correct |
7 |
Correct |
2 ms |
2384 KB |
Output is correct |
8 |
Correct |
1 ms |
2384 KB |
Output is correct |
9 |
Correct |
2 ms |
2384 KB |
Output is correct |
10 |
Correct |
2 ms |
2384 KB |
Output is correct |
11 |
Correct |
2 ms |
2384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
2552 KB |
Output is correct |
4 |
Correct |
2 ms |
2552 KB |
Output is correct |
5 |
Correct |
2 ms |
2384 KB |
Output is correct |
6 |
Correct |
2 ms |
2384 KB |
Output is correct |
7 |
Correct |
2 ms |
2552 KB |
Output is correct |
8 |
Correct |
1 ms |
2384 KB |
Output is correct |
9 |
Correct |
2 ms |
2384 KB |
Output is correct |
10 |
Correct |
1 ms |
2384 KB |
Output is correct |
11 |
Correct |
2 ms |
2384 KB |
Output is correct |
12 |
Correct |
32 ms |
6372 KB |
Output is correct |
13 |
Correct |
86 ms |
8124 KB |
Output is correct |
14 |
Correct |
49 ms |
6388 KB |
Output is correct |
15 |
Correct |
46 ms |
3704 KB |
Output is correct |
16 |
Correct |
56 ms |
6588 KB |
Output is correct |
17 |
Correct |
65 ms |
8892 KB |
Output is correct |
18 |
Correct |
61 ms |
6440 KB |
Output is correct |
19 |
Correct |
70 ms |
8124 KB |
Output is correct |
20 |
Correct |
54 ms |
6588 KB |
Output is correct |
21 |
Correct |
61 ms |
6588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
2556 KB |
Output is correct |
4 |
Correct |
1 ms |
2384 KB |
Output is correct |
5 |
Correct |
1 ms |
2552 KB |
Output is correct |
6 |
Correct |
1 ms |
2384 KB |
Output is correct |
7 |
Correct |
1 ms |
2384 KB |
Output is correct |
8 |
Correct |
1 ms |
2384 KB |
Output is correct |
9 |
Correct |
1 ms |
2384 KB |
Output is correct |
10 |
Correct |
1 ms |
2384 KB |
Output is correct |
11 |
Correct |
1 ms |
2384 KB |
Output is correct |
12 |
Correct |
1 ms |
2384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
2384 KB |
Output is correct |
4 |
Correct |
1 ms |
2384 KB |
Output is correct |
5 |
Correct |
1 ms |
2384 KB |
Output is correct |
6 |
Correct |
1 ms |
2384 KB |
Output is correct |
7 |
Correct |
1 ms |
2552 KB |
Output is correct |
8 |
Correct |
1 ms |
2384 KB |
Output is correct |
9 |
Correct |
1 ms |
2384 KB |
Output is correct |
10 |
Correct |
1 ms |
2384 KB |
Output is correct |
11 |
Correct |
1 ms |
2384 KB |
Output is correct |
12 |
Correct |
1 ms |
2552 KB |
Output is correct |
13 |
Correct |
1 ms |
2384 KB |
Output is correct |
14 |
Correct |
2 ms |
2384 KB |
Output is correct |
15 |
Correct |
2 ms |
2384 KB |
Output is correct |
16 |
Correct |
1 ms |
2384 KB |
Output is correct |
17 |
Correct |
1 ms |
2396 KB |
Output is correct |
18 |
Correct |
1 ms |
2384 KB |
Output is correct |
19 |
Correct |
2 ms |
2636 KB |
Output is correct |
20 |
Correct |
2 ms |
2520 KB |
Output is correct |
21 |
Correct |
2 ms |
2384 KB |
Output is correct |
22 |
Correct |
2 ms |
2384 KB |
Output is correct |
23 |
Correct |
2 ms |
2384 KB |
Output is correct |
24 |
Correct |
2 ms |
2384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
2384 KB |
Output is correct |
4 |
Correct |
1 ms |
2384 KB |
Output is correct |
5 |
Correct |
1 ms |
2384 KB |
Output is correct |
6 |
Correct |
1 ms |
2384 KB |
Output is correct |
7 |
Correct |
1 ms |
2384 KB |
Output is correct |
8 |
Correct |
1 ms |
2384 KB |
Output is correct |
9 |
Correct |
1 ms |
2384 KB |
Output is correct |
10 |
Correct |
1 ms |
2564 KB |
Output is correct |
11 |
Correct |
1 ms |
2384 KB |
Output is correct |
12 |
Correct |
1 ms |
2384 KB |
Output is correct |
13 |
Correct |
1 ms |
2384 KB |
Output is correct |
14 |
Correct |
1 ms |
2384 KB |
Output is correct |
15 |
Correct |
2 ms |
2384 KB |
Output is correct |
16 |
Correct |
1 ms |
2384 KB |
Output is correct |
17 |
Correct |
2 ms |
2384 KB |
Output is correct |
18 |
Correct |
1 ms |
2384 KB |
Output is correct |
19 |
Correct |
2 ms |
2384 KB |
Output is correct |
20 |
Correct |
3 ms |
2384 KB |
Output is correct |
21 |
Correct |
2 ms |
2384 KB |
Output is correct |
22 |
Correct |
2 ms |
2384 KB |
Output is correct |
23 |
Correct |
2 ms |
2384 KB |
Output is correct |
24 |
Correct |
2 ms |
2384 KB |
Output is correct |
25 |
Correct |
41 ms |
5300 KB |
Output is correct |
26 |
Correct |
65 ms |
6072 KB |
Output is correct |
27 |
Correct |
109 ms |
6988 KB |
Output is correct |
28 |
Correct |
106 ms |
7492 KB |
Output is correct |
29 |
Correct |
105 ms |
7404 KB |
Output is correct |
30 |
Correct |
63 ms |
4796 KB |
Output is correct |
31 |
Correct |
56 ms |
6836 KB |
Output is correct |
32 |
Correct |
96 ms |
7604 KB |
Output is correct |
33 |
Correct |
72 ms |
7132 KB |
Output is correct |
34 |
Correct |
103 ms |
7604 KB |
Output is correct |
35 |
Correct |
86 ms |
7092 KB |
Output is correct |
36 |
Correct |
91 ms |
7200 KB |
Output is correct |
37 |
Correct |
42 ms |
5996 KB |
Output is correct |