| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 33632 | sinhriv | Palembang Bridges (APIO15_bridge) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct Point{
int x;
int y;
void read(){
char read[5];
scanf("%s%d", read, &y);
x = (read[0] - 'A');
}
};
struct Person{
Point u;
Point v;
bool check(){
u.read();
v.read();
return (u.x == v.x);
}
int calc(int val){
return abs(u.y - val) + abs(v.y - val);
}
};
vector < pair < int, int > > a;
long long One(){
if(a.size() == 0) return 0;
int n = a.size();
vector < int > lst;
for(int i = 0; i < n; ++i){
lst.push_back(a[i].first);
lst.push_back(a[i].second);
}
sort(lst.begin(), lst.end());
long long ans = 0;
for(int i = 0; i < n + n; ++i){
ans += abs(lst[i] - lst[n]);
}
return ans + n;
}
struct lex_compare {
bool operator() (const pair < int, int >& x, const pair < int, int >&y) const {
if(x.first + x.second == y.first + y.second) {
if(x.first == y.first) return x.second < y.second;
return x.first < y.first;
}
return x.first + x.second < y.first + y.second;
}
};
struct second_compare {
bool operator() (const pair < int, int >& x, const pair < int, int >&y) const {
if(x.second != y.second) return x.second < y.second;
return x.first < y.first;
}
};
const int N = 2e5 + 10;
long long prefix[N];
int calc(pair < int, int > p, int val){
return abs(p.first - val) + abs(p.second - val);
}
long long Two(){
int n = a.size();
if(n == 0) return 0;
vector < int > lst;
for(int i = 0; i < n; ++i){
if(a[i].first > a[i].second){
swap(a[i].first, a[i].second);
}
lst.push_back(a[i].first);
lst.push_back(a[i].second);
}
sort(a.begin(), a.end());
sort(lst.begin(), lst.end());
lst.resize(unique(lst.begin(), lst.end()) - lst.begin());
for(int i = 0; i < n; ++i){
prefix[i] = a[i].first + a[i].second;
if(i > 0) prefix[i] += prefix[i - 1];
}
int small = 0;
long long sum = 0;
long long total = 0;
long long ans = 1e18;
multiset < int > tree;
for(int i = 0; i < lst.size(); ++i){
int x = lst[i];
while(small < n && a[small].first <= x){
sum += a[small].second;
total += a[small].first;
tree.insert(a[small].second);
++small;
}
while(!tree.empty() && *tree.begin() <= x){
sum -= *tree.begin() * 2;
tree.erase(tree.begin());
}
long long now = (1LL * small * x - total) + (sum + 1LL * (small - 2LL * tree.size()) * x);
multiset < pair < int, int >, lex_compare > inside;
multiset < pair < int, int >, second_compare > big;
long long sumBigX = 0;
long long sumBigY = 0;
long long sumInsideX = 0;
long long sumInsideY = 0;
long long sumOutside = 0;
int pter = small;
for(int j = i + 1; j < lst.size(); ++j){
int y = lst[j];
int where = lower_bound(a.begin(), a.end(), make_pair(y, 0)) - a.begin();
long long most = prefix[n - 1] - (where > 0 ? prefix[where - 1] : 0) - 2LL * (n - where) * y;
while(pter < where){
if(a[pter].second >= y){
big.insert(a[pter]);
sumBigX += a[pter].first;
sumBigY += a[pter].second;
}
else{
inside.insert(a[pter]);
sumInsideX += a[pter].first;
sumInsideY += a[pter].second;
}
++pter;
}
while(!big.empty() && big.begin() -> second < y){
sumBigX -= big.begin() -> first;
sumBigY -= big.begin() -> second;
sumInsideX += big.begin() -> first;
sumInsideY += big.begin() -> second;
inside.insert(*big.begin());
big.erase(big.begin());
}
while(!inside.empty()){
auto p = *inside.begin();
if(p.first + p.second <= x + y){
sumInsideX -= p.first;
sumInsideY -= p.second;
sumOutside += calc(p, x);
inside.erase(inside.begin());
continue;
}
break;
}
ans = min(ans, 2LL * inside.size() * y - sumInsideY - sumInsideX + sumOutside + sumBigY - sumBigX + most + now);
}
}
return n + ans;
}
int main(){
if(fopen("1.inp", "r")){
freopen("1.inp", "r", stdin);
}
long long out = 0;
int k, n;
scanf("%d%d", &k, &n);
for(int i = 1; i <= n; ++i){
Person x;
if(x.check()){
out += x.calc(x.u.y);
}
else{
a.emplace_back(x.u.y, x.v.y);
}
}
if(k == 1) cout << One() + out;
else{
cout << min(One(), Two()) + out;
}
return 0;
}