#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long long ll;
#define int long long
#define sz(x) (int)(x.size())
#define debug(x) cerr << (#x) << ": " << (x) << endl
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
struct traj {
int l, r;
double mid;
};
vector<traj> a;
int n, k, m;
int calcres(int mid) {
vector<int> vec1, vec2;
for (int i=0; i<=mid; i++) {
vec1.push_back(a[i].l);
vec1.push_back(a[i].r);
}
for (int i=mid+1; i<n; i++) {
vec2.push_back(a[i].l);
vec2.push_back(a[i].r);
}
int ans=0;
if (!vec1.empty()) {
sort(all(vec1));
int bridge=vec1[sz(vec1)/2-1];
for (int i=0; i<=mid; i++) {
ans+=abs(a[i].l-bridge)+abs(a[i].r-bridge);
}
}
if (!vec2.empty()) {
sort(all(vec2));
int bridge=vec2[sz(vec2)/2-1];
for (int i=mid+1; i<n; i++) {
ans+=abs(a[i].l-bridge)+abs(a[i].r-bridge);
}
}
// cout << mid << " " << ans << endl;
return ans;
}
int trinary_search(int l, int r) {
if (r-l<10) {
int ans=LLONG_MAX;
for (int i=l; i<=r; i++) {
ans=min(ans, calcres(i));
}
return ans;
}
int m1=l+(r-l)/3;
int m2=l+2*(r-l)/3;
int s1=calcres(m1);
int s2=calcres(m2);
if (s1<s2) return trinary_search(l, m2+1);
else return trinary_search(m1-1, r);
}
void solve() {
cin >> k >> n;
int res=0;
for (int i=0; i<n; i++) {
char aa, bb;
int aaa, bbb; cin >> aa >> aaa >> bb >> bbb;
if (aa==bb) {
res+=abs(aaa-bbb);
continue;
}
if (aaa>bbb) swap(aaa, bbb);
a.push_back(traj{aaa, bbb, (double)(aaa+bbb)/2.0});
}
n=sz(a);
res+=n;
if (n==0) {
cout << res << endl;
return;
}
sort(all(a), [](traj &A, traj &B){return A.mid<B.mid;});
if (k==1) cout << res+calcres(n-1) << endl;
else cout << res+trinary_search(0, n-1) << endl;
return;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;// cin >> tt;
while(tt--) solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 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 |
1 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 |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
524 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
19 ms |
7368 KB |
Output is correct |
13 |
Correct |
41 ms |
8652 KB |
Output is correct |
14 |
Correct |
33 ms |
7252 KB |
Output is correct |
15 |
Correct |
24 ms |
5068 KB |
Output is correct |
16 |
Correct |
24 ms |
7904 KB |
Output is correct |
17 |
Correct |
25 ms |
9344 KB |
Output is correct |
18 |
Correct |
32 ms |
8908 KB |
Output is correct |
19 |
Correct |
37 ms |
9004 KB |
Output is correct |
20 |
Correct |
32 ms |
8084 KB |
Output is correct |
21 |
Correct |
30 ms |
8384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
600 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
452 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 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 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 |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
500 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 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 |
0 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 |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |