#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
typedef vector<pl> vpl;
class ST {
private:
ll n;
int h;
vl st;
public:
ST(int n_) {
h = 1;n = 1;
while(n < n_) {
n <<= 1;
h++;
}
st.assign(2*n,0);
}
void up(ll p, ll val) {
p += n;
st[p] += val;
while(p > 1) {
st[p>>1] = st[p] + st[p^1];
p >>= 1;
}
}
ll get(int l, int r) {
ll res = 0;
for(l += n,r += n;l<r;l>>=1,r>>=1) {
if(l&1) {
res += st[l];
l++;
}
if(r&1) {
--r;
res += st[r];
}
}
return res;
}
int kth(int u) {
int p = 1;
for(int i=1;i<h;i++) {
p <<= 1;
if(st[p] < u) {
u -= st[p];p++;
}
}
return p-n;
}
inline ll size() {return n;}
};
vpl w;
ll wol() {
vl wa;
sort(w.begin(),w.end(),[&](const pl& a, const pl& b) {
return a.first + a.second < b.first + b.second;
});
for(int i=0;i<w.size();i++) {
wa.push_back(w[i].first);
wa.push_back(w[i].second);
}
map<ll,ll> mu;
sort(wa.begin(),wa.end());
for(int i=0;i<wa.size();i++) {
mu[wa[i]] = i;
}
vl rac(w.size()+1,0);
int rid = 0;
ST sa(wa.size()),sb(wa.size()),ra(wa.size()),rb(wa.size()),kt(wa.size());
ll res = 1e18;
for(int i=0;i<w.size();i++) {
int ia = mu[w[i].first];
int ib = mu[w[i].second];
sa.up(ib,w[i].second);
sb.up(ib,1);
kt.up(ib,1);
ra.up(ia,w[i].first);
rb.up(ia,1);
kt.up(ia,1);
int mi = kt.kth(i+1);
ll x = wa[mi];
rac[i+1] += 2*(x*sb.get(0,mi)-sa.get(0,mi) + ra.get(mi,ra.size()) - x*rb.get(mi,rb.size()));
}
sa = ST(wa.size());
sb = ST(wa.size());
ra = ST(wa.size());
rb = ST(wa.size());
kt = ST(wa.size());
for(int i=w.size()-1;i>=0;i--) {
int ia = mu[w[i].first];
int ib = mu[w[i].second];
sa.up(ib,w[i].second);
sb.up(ib,1);
kt.up(ib,1);
ra.up(ia,w[i].first);
rb.up(ia,1);
kt.up(ia,1);
int mi = kt.kth(w.size()-i);
ll x = wa[mi];
rac[i] += 2*(x*sb.get(0,mi)-sa.get(0,mi) + ra.get(mi,ra.size()) - x*rb.get(mi,rb.size()));
}
for(int i=0;i<rac.size();i++) {
res = min(res,rac[i]);
}
return res;
}
ll lol() {
vl wa;
for(int i=0;i<w.size();i++) {
wa.push_back(w[i].first);
wa.push_back(w[i].second);
}
sort(wa.begin(),wa.end());
ll pos = wa[wa.size()/2];
ll res = 0;
for(int i=0;i<w.size();i++) {
res += abs(w[i].first-pos) + abs(pos-w[i].second);
}
return res;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int k,n;
cin >> k >> n;
ll wad = 0;
ll nev = 0;
for(int i=0;i<n;i++) {
char ca,cb;
ll a,b;
cin >> ca >> a >> cb >> b;
if(ca == cb) {
wad += abs(a-b);
} else {
wad++;
nev += max(a,b)-min(a,b);
w.push_back({min(a,b),max(a,b)});
}
}
sort(w.begin(),w.end());
ll res = -1;
if(k == 1) {
res = lol();
} else {
res = wol();
res += nev;
}
cout << res+wad << '\n';
}
Compilation message
bridge.cpp: In function 'll wol()':
bridge.cpp:61:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<w.size();i++) {
~^~~~~~~~~
bridge.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<wa.size();i++) {
~^~~~~~~~~~
bridge.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<w.size();i++) {
~^~~~~~~~~
bridge.cpp:105:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<rac.size();i++) {
~^~~~~~~~~~~
bridge.cpp:71:6: warning: unused variable 'rid' [-Wunused-variable]
int rid = 0;
^~~
bridge.cpp: In function 'll lol()':
bridge.cpp:112:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<w.size();i++) {
~^~~~~~~~~
bridge.cpp:119:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<w.size();i++) {
~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
256 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
6 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
6 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
404 KB |
Output is correct |
9 |
Correct |
6 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
30 ms |
5748 KB |
Output is correct |
13 |
Correct |
63 ms |
7276 KB |
Output is correct |
14 |
Correct |
48 ms |
5996 KB |
Output is correct |
15 |
Correct |
37 ms |
4216 KB |
Output is correct |
16 |
Correct |
38 ms |
6636 KB |
Output is correct |
17 |
Correct |
48 ms |
7276 KB |
Output is correct |
18 |
Correct |
45 ms |
7020 KB |
Output is correct |
19 |
Correct |
53 ms |
7272 KB |
Output is correct |
20 |
Correct |
40 ms |
6888 KB |
Output is correct |
21 |
Correct |
51 ms |
7144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
512 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
640 KB |
Output is correct |
14 |
Correct |
6 ms |
568 KB |
Output is correct |
15 |
Correct |
7 ms |
768 KB |
Output is correct |
16 |
Correct |
5 ms |
512 KB |
Output is correct |
17 |
Correct |
5 ms |
512 KB |
Output is correct |
18 |
Correct |
5 ms |
512 KB |
Output is correct |
19 |
Correct |
6 ms |
640 KB |
Output is correct |
20 |
Correct |
6 ms |
768 KB |
Output is correct |
21 |
Correct |
7 ms |
768 KB |
Output is correct |
22 |
Correct |
6 ms |
768 KB |
Output is correct |
23 |
Correct |
5 ms |
616 KB |
Output is correct |
24 |
Correct |
9 ms |
696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
640 KB |
Output is correct |
14 |
Correct |
6 ms |
640 KB |
Output is correct |
15 |
Correct |
7 ms |
664 KB |
Output is correct |
16 |
Correct |
5 ms |
512 KB |
Output is correct |
17 |
Correct |
6 ms |
640 KB |
Output is correct |
18 |
Correct |
6 ms |
512 KB |
Output is correct |
19 |
Correct |
6 ms |
640 KB |
Output is correct |
20 |
Correct |
7 ms |
768 KB |
Output is correct |
21 |
Correct |
7 ms |
800 KB |
Output is correct |
22 |
Correct |
7 ms |
768 KB |
Output is correct |
23 |
Correct |
6 ms |
640 KB |
Output is correct |
24 |
Correct |
6 ms |
768 KB |
Output is correct |
25 |
Correct |
108 ms |
29668 KB |
Output is correct |
26 |
Correct |
131 ms |
30052 KB |
Output is correct |
27 |
Correct |
578 ms |
42076 KB |
Output is correct |
28 |
Correct |
567 ms |
44004 KB |
Output is correct |
29 |
Correct |
572 ms |
43876 KB |
Output is correct |
30 |
Correct |
244 ms |
22636 KB |
Output is correct |
31 |
Correct |
111 ms |
30564 KB |
Output is correct |
32 |
Correct |
281 ms |
43812 KB |
Output is correct |
33 |
Correct |
255 ms |
43364 KB |
Output is correct |
34 |
Correct |
281 ms |
43360 KB |
Output is correct |
35 |
Correct |
121 ms |
30824 KB |
Output is correct |
36 |
Correct |
281 ms |
43624 KB |
Output is correct |
37 |
Correct |
96 ms |
29792 KB |
Output is correct |