#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
const long long inf=1e15;
struct person{
char s;
int from;
char t;
int to;
}a[MAXN];
struct event{
int pos;
int id,type;
inline friend bool operator < (event fr,event sc){
return fr.pos<sc.pos;
}
};
int n,k,br[MAXN],br2[MAXN],l,r,id;
char type;
long long sum,last,lasst,lt,rt,cntl,cntr,ans;
long long sum1,sum2,mid;
vector<event> v;
pair<int,int> curr;
set< pair<int,int> > s1,s2;
set< pair<int,int> >::iterator it;
void solve1(){
ans=inf;
if(v.empty()){
cout<<sum<<"\n";
return;
}
last=v[int(v.size())-1].pos;
for(int i=int(v.size())-1;i>=0;i--){
rt+=(last-v[i].pos)*cntr;
br[v[i].id]++;
if(br[v[i].id]==2){
cntr+=2;
rt+=a[v[i].id].from+a[v[i].id].to-2*v[i].pos;
rt++;
}
last=v[i].pos;
}
last=v[0].pos;
l=r=0;
for(int i=0;i<v.size();i++){
lt+=(v[i].pos-last)*cntl;
rt-=(v[i].pos-last)*cntr;
br[v[i].id]--;
if(br[v[i].id]==1){
rt-=abs(a[v[i].id].from-a[v[i].id].to); cntr-=2; rt--;
sum+=abs(a[v[i].id].from-a[v[i].id].to)+1;
}else{
sum-=abs(a[v[i].id].from-a[v[i].id].to)+1;
lt+=abs(a[v[i].id].from-a[v[i].id].to); cntl+=2;
lt++;
}
ans=min(ans,lt+rt+sum);
last=v[i].pos;
}
cout<<ans<<"\n";
}
void addleft(long long val,int id){
s1.insert({val,id});
sum1+=val;
}
void remleft(){
it=s1.end(); it--;
curr=*it;
sum1-=curr.first;
s1.erase(it);
}
void addright(long long val,int id){
s2.insert({val,id});
sum2+=val;
}
void remright(){
it=s2.begin();
curr=*it;
sum2-=curr.first;
s2.erase(it);
}
void balance(long long e,long long t){
while(!s2.empty()){
it=s2.begin();
curr=*it;
if(curr.first>e+t)break;
addleft(curr.first,curr.second);
remright();
}
while(!s1.empty()){
it=s1.end(); it--;
curr=*it;
if(curr.first<=e+t)break;
addright(curr.first,curr.second);
remleft();
}
}
void moveright(){
br[v[r].id]--;
if(br[v[r].id]==1){
rt-=abs(a[v[r].id].from-a[v[r].id].to); cntr-=2; rt--;
sum+=abs(a[v[r].id].from-a[v[r].id].to)+1;
}else if(br2[v[r].id]==0){
addleft(a[v[r].id].from+a[v[r].id].to,v[r].id);
balance(v[l].pos,v[r].pos);
}
last=v[r].pos; r++;
rt-=(v[r].pos-last)*cntr;
}
void moveleft(){
last=v[r].pos; r--;
rt+=(last-v[r].pos)*cntr;
br[v[r].id]++;
if(br[v[r].id]==2){
if(s1.find({a[v[r].id].from+a[v[r].id].to,v[r].id})!=s1.end()){
sum1-=a[v[r].id].from+a[v[r].id].to;
s1.erase({a[v[r].id].from+a[v[r].id].to,v[r].id});
}
if(s2.find({a[v[r].id].from+a[v[r].id].to,v[r].id})!=s2.end()){
sum2-=a[v[r].id].from+a[v[r].id].to;
s2.erase({a[v[r].id].from+a[v[r].id].to,v[r].id});
}
cntr+=2;
rt+=a[v[r].id].from+a[v[r].id].to-2*v[r].pos;
rt++;
}
}
void solve2(){
ans=inf;
if(v.empty()){
cout<<sum<<"\n";
return;
}
last=v[int(v.size())-1].pos;
for(int i=int(v.size())-1;i>=1;i--){
rt+=(last-v[i].pos)*cntr;
br[v[i].id]++;
if(br[v[i].id]==2){
cntr+=2;
rt+=a[v[i].id].from+a[v[i].id].to-2*v[i].pos;
rt++;
}
last=v[i].pos;
}
lasst=v[0].pos;
l=0; r=1;
for(int i=0;i<v.size();i++){
l=i;
lt+=(v[i].pos-lasst)*cntl;
br2[v[i].id]++;
if(br2[v[i].id]==1){
if(s1.find({a[v[i].id].from+a[v[i].id].to,v[i].id})!=s1.end()){
sum1-=a[v[i].id].from+a[v[i].id].to;
s1.erase({a[v[i].id].from+a[v[i].id].to,v[i].id});
}
if(s2.find({a[v[i].id].from+a[v[i].id].to,v[i].id})!=s2.end()){
sum2-=a[v[i].id].from+a[v[i].id].to;
s2.erase({a[v[i].id].from+a[v[i].id].to,v[i].id});
}
sum+=abs(a[v[i].id].from-a[v[i].id].to)+1;
}else{
sum-=abs(a[v[i].id].from-a[v[i].id].to)+1;
lt+=abs(a[v[i].id].from-a[v[i].id].to); cntl+=2;
lt++;
}
for(int f=i+1;f<v.size();f++){
mid=(long long) sum1-int(s1.size())*v[l].pos*2+2*int(s2.size())*v[r].pos-sum2+int(s1.size())+int(s2.size());
//cout<<l<<" "<<r<<" "<<lt<<" "<<mid<<" "<<rt<<" "<<sum<<"\n";
//cout<<s1.size()<<" "<<s2.size()<<"\n";
ans=min(ans,lt+rt+mid+sum);
if(f<v.size()-1)moveright();
}
for(int f=i+3;f<v.size();f++){
moveleft();
}
lasst=v[i].pos;
}
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>k>>n;
for(int i=1;i<=n;i++){
cin>>a[i].s>>a[i].from>>a[i].t>>a[i].to;
if(a[i].s==a[i].t){
sum+=abs(a[i].from-a[i].to);
}else{
v.push_back({a[i].from,i,1});
v.push_back({a[i].to,i,2});
}
}
sort(v.begin(),v.end());
if(k==1){
solve1();
}else{
solve2();
}
return 0;
}
Compilation message
bridge.cpp: In function 'void solve1()':
bridge.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=0;i<v.size();i++){
| ~^~~~~~~~~
bridge.cpp: In function 'void solve2()':
bridge.cpp:176:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | for(int i=0;i<v.size();i++){
| ~^~~~~~~~~
bridge.cpp:199:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | for(int f=i+1;f<v.size();f++){
| ~^~~~~~~~~
bridge.cpp:204:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
204 | if(f<v.size()-1)moveright();
| ~^~~~~~~~~~~
bridge.cpp:206:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
206 | for(int f=i+3;f<v.size();f++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
24 ms |
4712 KB |
Output is correct |
| 13 |
Correct |
44 ms |
4672 KB |
Output is correct |
| 14 |
Correct |
32 ms |
4552 KB |
Output is correct |
| 15 |
Correct |
26 ms |
2904 KB |
Output is correct |
| 16 |
Correct |
31 ms |
4636 KB |
Output is correct |
| 17 |
Correct |
29 ms |
4664 KB |
Output is correct |
| 18 |
Correct |
36 ms |
4676 KB |
Output is correct |
| 19 |
Correct |
43 ms |
4636 KB |
Output is correct |
| 20 |
Correct |
30 ms |
4664 KB |
Output is correct |
| 21 |
Correct |
37 ms |
4628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
