#include<bits/stdc++.h>
#define all(aa) aa.begin(), aa.end()
#define endl ("\n")
#define pb push_back
typedef long long ll;
const int maxn = 1e5 + 5;
using namespace std;
int n, k;
vector<pair<ll, ll>> v;
vector<ll> u;
multiset<pair<ll, ll>> nxt, in;
multiset<pair<ll, pair<ll, ll>>> vis; // vis r'ye gore artan come l'ye gore artan
ll lft, rgt, lst;
ll ans = LONG_LONG_MAX, cur, rem;
ll dst(pair<ll, ll> p, ll ind){
if(p.first <= ind && ind <= p.second) return 0;
return 2*min(abs(p.first - ind), abs(p.second - ind));
}
int main(){
cin >> k >> n;
for(int i = 0; i < n; i++){
char c1, c2;
int a, b;
cin >> c1 >> a >> c2 >> b;
if(b > a) swap(a, b);
rem+=a-b;
if(c1!=c2){
++rem;
v.pb({b, a});
u.pb(a), u.pb(b);
}
}
rgt = n = v.size();
sort(all(u));
sort(all(v));
if(k == 2){
// cerr << rem << endl;
for(int l = 0; l < 2*n; l++){
cur = 0;
lft = rgt = 0, lst = u[l];
for(int i = 0; i < n; i++){
cur += dst(v[i], u[l]);
if(u[l] < v[i].first){
nxt.insert(v[i]);
rgt++;
}
}
for(int r = l+1; r < 2*n; r++){
cur += lft*2*(u[r] - lst) - rgt*2*(u[r] - lst);
while(!nxt.empty() && (*nxt.begin()).first == u[r]){
pair<ll, ll> p = *nxt.begin();
in.insert({p.second, p.first});
nxt.erase(nxt.begin());
rgt--;
}
while(!in.empty() && (*in.begin()).first == u[r]){
pair<ll, ll> p = *in.begin();
in.erase(in.begin());
pair<ll, ll> fix = {p.second, p.first};
vis.insert({dst(fix, u[l]) - dst(fix, u[r]), fix});
lft++;
}
while(!vis.empty() && dst((*vis.begin()).second, u[r]) > dst((*vis.begin()).second, u[l]) ){
pair<ll, ll> p = (*vis.begin()).second;
lft--;
vis.erase(vis.begin());
cur += dst(p, u[l]) - dst(p, u[r]);
}
ans = min(ans, cur);
lst = u[r];
}
vis.clear();
nxt.clear();
in.clear();
}
cout << ans + rem << endl;
// cout << ans << endl;
} else{
cur = rem;
rgt = n, lst = lft = 0;
multiset<pair<ll, ll>> come;
multiset<ll> vs;
for(int i = 0; i < n; i++){
come.insert(v[i]);
cur+=2*v[i].first;
}
ans = cur;
for(int i = 0; i < 2*n; i++){
cur += lft*2*(u[i] - lst) - rgt*2*(u[i] - lst);
while(!come.empty() && (*come.begin()).first == u[i]){
pair<ll, ll> p = *come.begin();
vs.insert({p.second});
come.erase(come.find(p));
rgt--;
}
while(!vs.empty() && *vs.begin() == u[i]){
lft++;
vs.erase(vs.begin());
}
ans = min(ans, cur);
lst = u[i];
}
cout << ans << endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
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 |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
2 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 |
344 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 |
76 ms |
9632 KB |
Output is correct |
13 |
Correct |
126 ms |
9780 KB |
Output is correct |
14 |
Correct |
99 ms |
8872 KB |
Output is correct |
15 |
Correct |
71 ms |
5816 KB |
Output is correct |
16 |
Correct |
84 ms |
9644 KB |
Output is correct |
17 |
Correct |
93 ms |
9664 KB |
Output is correct |
18 |
Correct |
101 ms |
9796 KB |
Output is correct |
19 |
Correct |
106 ms |
9668 KB |
Output is correct |
20 |
Correct |
91 ms |
9648 KB |
Output is correct |
21 |
Correct |
99 ms |
9772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |