#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (100005)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
inline ll myabs(const ll& n) { return n < 0 ? -n : n; }
ll d[2][MAXN];
int A[MAXN], B[MAXN], P[MAXN];
int N, K;
ll Ans;
void input() {
scanf("%d%d", &K, &N);
int cnt = 0; for(int i = 0; i < N; i++) {
int x, y; char a, b; scanf(" %c%d %c%d", &a, &x, &b, &y);
if(a == b) { Ans += myabs(x-y); continue; }
A[cnt] = x; B[cnt] = y; cnt++;
}
N = cnt;
}
void process1() {
vector<int> V;
for(int i = 0; i < N; i++) { V.pb(A[i]); V.pb(B[i]); }
sorv(V); const int X = V[sz(V)/2];
for(int i = 0; i < N; i++) Ans += myabs((ll)A[i] - X) + myabs((ll)B[i] - X);
Ans += sz(V)/2;
}
multiset<int> Q;
void meanF(ll d[]) {
multiset<int>().swap(Q);
Q.insert(A[P[0]]); Q.insert(B[P[0]]);
auto it = Q.begin(); d[0] = myabs((ll)A[P[0]] - (*it)) + myabs((ll)B[P[0]] - (*it));
for(int p_i = 1; p_i < N; p_i++) {
const int &idx = P[p_i]; ll &ret = d[p_i];
if(A[idx] > B[idx]) swap(A[idx], B[idx]);
if(B[idx] <= (*it)) {
const int prv = *it;
Q.insert(A[idx]); Q.insert(B[idx]);
it--; ret = d[p_i-1] + (ll)(*it)*2 - A[idx] - B[idx] + ((ll)prv-(*it))*2;
} else if((*it) <= A[idx]) {
Q.insert(A[idx]); Q.insert(B[idx]);
it++; ret = d[p_i-1] + A[idx] + B[idx] - (ll)(*it)*2;
} else {
Q.insert(A[idx]); Q.insert(B[idx]);
ret = d[p_i-1] + B[idx] - A[idx];
}
}
vector<int> V;
for(int i = 0; i < N; i++) {
V.pb(A[P[i]]); V.pb(B[P[i]]);
sorv(V);
const int X = V[sz(V)/2];
ll &ret = d[i]; ret = 0;
for(const int& v : V) ret += myabs((ll)X - v);
}
}
void process2() {
for(int i = 0; i < N; i++) P[i] = i;
sort(P, P+N, [&](const int& a, const int& b) -> bool {
return (A[a]+B[a]) < (A[b]+B[b]);
});
meanF(d[0]); reverse(P, P+N); meanF(d[1]); reverse(d[1], d[1]+N); reverse(P, P+N);
ll ret = d[0][0] + d[1][1];
for(int i = 0; i+1 < N; i++) {
upmin(ret, d[0][i] + d[1][i+1]);
}
upmin(ret, d[0][3]); upmin(ret, d[1][0]);
Ans += ret + N;
}
int main() {
input();
if(!N); else if(1 == N) { Ans += myabs(A[0] - B[0]) + 1; }
else if(1 == K) process1(); else process2();
printf("%lld\n", Ans);
return 0;
}
Compilation message
bridge.cpp: In function 'void input()':
bridge.cpp:41:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &K, &N);
^
bridge.cpp:43:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; char a, b; scanf(" %c%d %c%d", &a, &x, &b, &y);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
4760 KB |
Output is correct |
2 |
Correct |
0 ms |
4760 KB |
Output is correct |
3 |
Correct |
0 ms |
4760 KB |
Output is correct |
4 |
Correct |
0 ms |
4760 KB |
Output is correct |
5 |
Correct |
0 ms |
4760 KB |
Output is correct |
6 |
Correct |
0 ms |
4760 KB |
Output is correct |
7 |
Correct |
0 ms |
4760 KB |
Output is correct |
8 |
Correct |
0 ms |
4760 KB |
Output is correct |
9 |
Correct |
0 ms |
4760 KB |
Output is correct |
10 |
Correct |
0 ms |
4760 KB |
Output is correct |
11 |
Correct |
0 ms |
4760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
4760 KB |
Output is correct |
2 |
Correct |
0 ms |
4760 KB |
Output is correct |
3 |
Correct |
0 ms |
4760 KB |
Output is correct |
4 |
Correct |
0 ms |
4760 KB |
Output is correct |
5 |
Correct |
0 ms |
4760 KB |
Output is correct |
6 |
Correct |
0 ms |
4760 KB |
Output is correct |
7 |
Correct |
0 ms |
4760 KB |
Output is correct |
8 |
Correct |
0 ms |
4760 KB |
Output is correct |
9 |
Correct |
0 ms |
4760 KB |
Output is correct |
10 |
Correct |
0 ms |
4760 KB |
Output is correct |
11 |
Correct |
0 ms |
4760 KB |
Output is correct |
12 |
Correct |
33 ms |
6380 KB |
Output is correct |
13 |
Correct |
63 ms |
6380 KB |
Output is correct |
14 |
Correct |
39 ms |
6380 KB |
Output is correct |
15 |
Correct |
36 ms |
5612 KB |
Output is correct |
16 |
Correct |
49 ms |
6380 KB |
Output is correct |
17 |
Correct |
49 ms |
6380 KB |
Output is correct |
18 |
Correct |
56 ms |
6380 KB |
Output is correct |
19 |
Correct |
59 ms |
6380 KB |
Output is correct |
20 |
Correct |
49 ms |
6380 KB |
Output is correct |
21 |
Correct |
66 ms |
6380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
4760 KB |
Output is correct |
2 |
Correct |
0 ms |
4760 KB |
Output is correct |
3 |
Incorrect |
0 ms |
4760 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
4760 KB |
Output is correct |
2 |
Correct |
0 ms |
4760 KB |
Output is correct |
3 |
Incorrect |
0 ms |
4760 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
4760 KB |
Output is correct |
2 |
Correct |
0 ms |
4760 KB |
Output is correct |
3 |
Incorrect |
0 ms |
4760 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |