#include <bits/stdc++.h>
#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 10007
#define left lleft
#define right rright
#define INF 2000000000
#define LINF 1000000000000000000LL
#define next nnext
using namespace std;
int N,K,rear;
lld memo,ans,sum;
lld cnt1,cnt2,cnt3,cnt4;
vector<int> X;
struct IN{
int x,y;
}in[100002];
struct data{
int x,num;
}a[100002],b[100002];
void process1(){
for(int i=1; i<=N; i++){
sum += (a[i].x+b[i].x-X[0]-X[0]);
if(a[i].x > X[0]) cnt2++;
}
ans = min(ans,sum);
int tx,ty;
tx = ty = 0;
while(1){
if(tx == N || a[tx+1].x > X[0]) break;
tx++;
}
for(int i=1; i<X.size(); i++){
ans += (2*cnt1); ans -= (2*cnt2);
while(1){
if(tx == N || a[tx+1].x > X[i]) break;
tx++;
cnt2--; sum -= 2;
}
while(1){
if(ty == N || b[ty+1].x > X[i-1]) break;
ty++;
cnt1++; sum += 2;
}
ans = min(ans,sum);
}
}
int main(){
scanf("%d %d",&K,&N);
for(int i=1; i<=N; i++){
int x,y;
char op1,op2;
scanf("\n%c %d %c %d",&op1,&x,&op2,&y);
if(x > y) swap(x,y);
if(op1 == op2) memo += (y-x);
else{
rear++;
a[rear].x = x; a[rear].num = i;
b[rear].x = y; b[rear].num = i;
X.pb(x); X.pb(y);
}
}
N = rear; ans = LINF;
sort(X.begin(),X.end());
X.erase(unique(X.begin(),X.end()),X.end());
sort(a+1,a+N+1,[&](data &x,data &y){
return x.x < y.x;
});
sort(b+1,b+N+1,[&](data &x,data &y){
return x.x < y.x;
});
if(K == 1) process1();
ans += memo;
printf("%lld\n",ans);
return 0;
}
Compilation message
bridge.cpp: In function 'void process1()':
bridge.cpp:38:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<X.size(); i++){
^
bridge.cpp: In function 'int main()':
bridge.cpp:55:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&K,&N);
^
bridge.cpp:59:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n%c %d %c %d",&op1,&x,&op2,&y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4368 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4368 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
4368 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4368 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4368 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
4368 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
4368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
4368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
4368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
