#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
typedef long long ll;
using namespace std;
using pii = pair<int,int>;
const int N = 1e5 + 5, M = 2e5 + 5;
int a[M], m, cp[M], to_rem[N];
bool ok[N];
ll bit[2][M];
pii P[N], V[M];
int pos(int x){ return upper_bound(cp, cp+m, x) - cp;}
ll upd(int x, int i, ll val){ for(; i<M; i+=i&-i) bit[x][i] += val;}
ll qry(int x, int i){ ll res = 0; for(; i; i-=i&-i) res += bit[x][i]; return res;}
int _find(int k){
int sum = 0, i = 0;
for(int j = 18; j>=0; --j){
if(i+(1<<j) < M && sum + bit[0][i+(1<<j)] < k) sum += bit[0][i+=(1<<j)];
}
return i + 1;
}
signed main(){
int k, n; m = 0; scanf("%d %d", &k, &n);
if(k == 1){
ll tot = 0; char c[2];
for(int i = 0, p[2]; i<n; ++i){
scanf(" %c %d %c %d", c, p, c+1, p+1); if(p[0] > p[1]) swap(p[0], p[1]);
if(c[0] == c[1]) tot += p[1] - p[0];
else{ a[m++] = p[0]; a[m++] = p[1];}
}
sort(a, a+m);
for(int i = 0; i<m; ++i) tot += abs(a[i] - a[m/2 - 1]);
printf("%lld", tot + m/2);
}else{
ll tot = 0, sum[2] = {0, 0};
for(int i = 0, p[2]; i<n; ++i){
char c[2];
scanf(" %c %d %c %d", c, p, c+1, p+1); if(p[0] > p[1]) swap(p[0], p[1]);
if(c[0] == c[1]) tot += p[1] - p[0];
else{
cp[m] = p[0]; V[m++] = mp(p[0], i);
cp[m] = p[1]; V[m++] = mp(p[1], i);
P[i] = mp(p[0], p[1]);
ok[i] = true;
++tot;
}
}
int sz = m, cnt = 0;
sort(cp, cp+m); m = unique(cp, cp+m) - cp;
sort(V, V+sz);
for(int i = 0; i<n; ++i){
if(ok[i]){
int idx[2] = {pos(P[i].F), pos(P[i].S)};
upd(0, idx[0], +1); upd(0, idx[1], +1);
upd(1, idx[0], +P[i].F); upd(1, idx[1], +P[i].S);
cnt += 2;
}
}
int I = _find((cnt+1)/2);
ll fp = qry(0, I) * cp[I-1] - qry(1, I);
ll sp = (qry(1, M-1) - qry(1, I)) - (qry(0, M-1) - qry(0, I)) * cp[I-1];
ll md = fp + sp, not_md = 0, mn = 2e18;
set<int> s;
for(int i = 0, j; i<sz; ){
int t = 0;
for(j = i; V[j].F == V[i].F; ++j){
if(s.find(V[j].S) == s.end()){
s.insert(V[j].S);
int idx[2] = {pos(P[V[j].S].F), pos(P[V[j].S].S)};
upd(0, idx[0], -1); upd(0, idx[1], -1);
upd(1, idx[0], -P[i].F); upd(1, idx[1], -P[i].S);
cnt -= 2;
not_md += P[V[j].S].S - P[V[j].S].F;
}else{
to_rem[t++] = V[j].S;
}
}
//
I = _find((cnt+1)/2);
fp = qry(0, I) * cp[I-1] - qry(1, I);
sp = (qry(1, M-1) - qry(1, I)) - (qry(0, M-1) - qry(0, I)) * cp[I-1];
md = fp + sp;
mn = min(mn, md + not_md);
//
for(int w = 0; w<t; ++w){
s.erase(to_rem[w]);
int idx[2] = {pos(P[to_rem[j]].F), pos(P[to_rem[j]].S)};
upd(0, idx[0], +1); upd(0, idx[1], +1);
upd(1, idx[0], +P[i].F); upd(1, idx[1], +P[i].S);
cnt += 2;
not_md -= P[to_rem[w]].S - P[to_rem[w]].F;
}
//
i = j;
}
printf("%lld", tot + mn);
}
}
Compilation message
bridge.cpp: In function 'll upd(int, int, ll)':
bridge.cpp:14:68: warning: no return statement in function returning non-void [-Wreturn-type]
14 | ll upd(int x, int i, ll val){ for(; i<M; i+=i&-i) bit[x][i] += val;}
| ^
bridge.cpp: In function 'int main()':
bridge.cpp:37:15: warning: unused variable 'sum' [-Wunused-variable]
37 | ll tot = 0, sum[2] = {0, 0};
| ^~~
bridge.cpp:25:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | int k, n; m = 0; scanf("%d %d", &k, &n);
| ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:29:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | scanf(" %c %d %c %d", c, p, c+1, p+1); if(p[0] > p[1]) swap(p[0], p[1]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:40:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf(" %c %d %c %d", c, p, c+1, p+1); if(p[0] > p[1]) swap(p[0], p[1]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
460 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 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 |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
456 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
18 ms |
1984 KB |
Output is correct |
| 13 |
Correct |
33 ms |
3416 KB |
Output is correct |
| 14 |
Correct |
22 ms |
2140 KB |
Output is correct |
| 15 |
Correct |
21 ms |
2140 KB |
Output is correct |
| 16 |
Correct |
19 ms |
2880 KB |
Output is correct |
| 17 |
Correct |
23 ms |
3508 KB |
Output is correct |
| 18 |
Correct |
25 ms |
3040 KB |
Output is correct |
| 19 |
Correct |
32 ms |
3408 KB |
Output is correct |
| 20 |
Correct |
22 ms |
2868 KB |
Output is correct |
| 21 |
Correct |
27 ms |
3164 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 |
1 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 |
- |
