#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 * int(inside.size()) * y - sumInsideY - sumInsideX + sumOutside + sumBigY - sumBigX + most + now);
}
}
return n + ans;
}
long long preCalc[N];
struct PersistentIT{
int cnt, root, n;
int L[N * 10];
int R[N * 10];
vector < pair < int, int > > save;
pair < long long, int > value[N * 10];
#define mid ((l + r) >> 1)
void build(int &x, int l, int r){
if(x == 0) x = ++cnt;
if(l == r) {
value[x] = make_pair(0, 0);
return;
}
build(L[x], l, mid);
build(R[x], mid + 1, r);
}
pair < int, int > combine(pair < int, int > u, pair < int, int > v){
u.first += v.first;
u.second += v.second;
return u;
}
void upd(int &x, int old, int l, int r, int pos, pair < int, int > val){
if(l > pos || r < pos){
x = old;
return;
}
x = ++cnt;
value[x] = combine(value[old], val);
if(l == r){
return;
}
upd(L[x], L[old], l, mid, pos, val);
upd(R[x], R[old], mid + 1, r, pos, val);
value[x] = combine(value[L[x]], value[R[x]]);
}
pair < int, int > sub(pair < int, int > u, pair < int, int > v){
u.first -= v.first;
u.second -= v.second;
return u;
}
pair < int, int > query(int x, int l, int r, int u, int v){
if(l > v || r < u){
return make_pair(0, 0);
}
if(l >= u && r <= v) {
return value[x];
}
return combine(query(L[x], l, mid, u, v), query(R[x], mid + 1, r, u, v));
}
void add(int x){
save.emplace_back(x, root);
}
void Init(int sz){
n = sz;
cnt = root = 1;
build(root, 1, n);
add(0);
}
void update(int pos, int val){
upd(root, root, 1, n, pos, make_pair(val, 1));
}
pair < int, int > ask(int x, int l, int r){
if(x < 0) return make_pair(0, 0);
return query(x, 1, n, l, r);
}
int fin(int x){
int p = lower_bound(save.begin(), save.end(), make_pair(x, -1)) - save.begin();
return save[p].second;
}
pair < int, int > query2D(int l, int r, int u, int v){
++l; ++r;
//cout << l << " " << r << " " << u << " " << v << endl;
if(l > r || u > v) return make_pair(0, 0);
return sub(ask(fin(r), u, v), ask(fin(l - 1), u, v));
}
}treeInside, treeBig, treeSum;
vector < int > lst, arr;
int getIdx(int x){
return lower_bound(lst.begin(), lst.end(), x) - lst.begin() + 1;
}
long long sumX[N];
long long sumY[N];
long long Calc(int x, int y){
int pos = upper_bound(a.begin(), a.end(), make_pair(x + 1, -1)) - a.begin() - 1;
long long now = preCalc[lower_bound(lst.begin(), lst.end(), x) - lst.begin()];
int p = lower_bound(a.begin(), a.end(), make_pair(y, -1)) - a.begin();
long long tot = prefix[a.size() - 1] - (p > 0 ? prefix[p - 1] : 0) - 2LL * (a.size() - p) * y;
long long Outside = treeBig.query2D(pos + 1, p - 1, getIdx(y), lst.size()).first;
auto current = treeInside.query2D(pos + 1, p - 1, 1, getIdx(x + y));
long long solve = current.first - 2LL * current.second * x;
auto smaller = treeSum.query2D(pos + 1, p - 1, getIdx(y), lst.size());
long long other = sumX[p - 1] - sumX[pos] + sumY[p - 1] - sumY[pos];
//cout << other - current.first - small<< endl;
other = 2LL * (p - 1 - pos - current.second - smaller.second) * y - (other - current.first - smaller.first);
return now + tot + Outside + solve + other;
}
long long Three(){
int n = a.size();
if(n == 0) return 0;
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());
arr = lst;
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;
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);
preCalc[i] = now;
}
for(int i = 0; i < n; ++i){
lst.push_back(a[i].first + a[i].second);
}
sort(lst.begin(), lst.end());
lst.resize(unique(lst.begin(), lst.end()) - lst.begin());
treeSum.Init(lst.size());
treeBig.Init(lst.size());
treeInside.Init(lst.size());
for(int i = 0; i < n; ++i){
treeSum.update(getIdx(a[i].second), a[i].first + a[i].second);
treeBig.update(getIdx(a[i].second), a[i].second - a[i].first);
//cout << getIdx(a[i].second) << " " << i + 1 << endl;
treeInside.update(getIdx(a[i].first + a[i].second), a[i].first + a[i].second);
treeBig.add(i + 1);
treeSum.add(i + 1);
treeInside.add(i + 1);
sumX[i] = a[i].first;
sumY[i] = a[i].second;
if(i > 0){
sumX[i] += sumX[i - 1];
sumY[i] += sumY[i - 1];
}
}
long long ans = 1e18;
for(int i = 0; i < arr.size(); ++i){
for(int j = i + 1; j < arr.size(); ++j){
ans = min(ans, Calc(arr[i], arr[j]));
}
}
return ans + n;
}
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{
long long ans = One();
if(a.size() <= 1000){
ans = min(ans, Three());
}
else{
ans = min(ans, Three());
}
cout << ans + out;
}
return 0;
}
Compilation message
bridge.cpp: In function 'long long int Two()':
bridge.cpp:115:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < lst.size(); ++i){
^
bridge.cpp:141:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = i + 1; j < lst.size(); ++j){
^
bridge.cpp: In function 'long long int Three()':
bridge.cpp:362:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < lst.size(); ++i){
^
bridge.cpp:418:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < arr.size(); ++i){
^
bridge.cpp:419:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = i + 1; j < arr.size(); ++j){
^
bridge.cpp: In function 'int main()':
bridge.cpp:429:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("1.inp", "r", stdin);
^
bridge.cpp:435:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &k, &n);
^
bridge.cpp: In member function 'void Point::read()':
bridge.cpp:11:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s%d", read, &y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
148952 KB |
Output is correct |
| 2 |
Correct |
9 ms |
148952 KB |
Output is correct |
| 3 |
Correct |
6 ms |
148952 KB |
Output is correct |
| 4 |
Correct |
23 ms |
148952 KB |
Output is correct |
| 5 |
Correct |
9 ms |
148952 KB |
Output is correct |
| 6 |
Correct |
6 ms |
148952 KB |
Output is correct |
| 7 |
Correct |
16 ms |
148952 KB |
Output is correct |
| 8 |
Correct |
6 ms |
148952 KB |
Output is correct |
| 9 |
Correct |
9 ms |
148952 KB |
Output is correct |
| 10 |
Correct |
0 ms |
148952 KB |
Output is correct |
| 11 |
Correct |
9 ms |
148952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
148952 KB |
Output is correct |
| 2 |
Correct |
9 ms |
148952 KB |
Output is correct |
| 3 |
Correct |
6 ms |
148952 KB |
Output is correct |
| 4 |
Correct |
9 ms |
148952 KB |
Output is correct |
| 5 |
Correct |
6 ms |
148952 KB |
Output is correct |
| 6 |
Correct |
6 ms |
148952 KB |
Output is correct |
| 7 |
Correct |
13 ms |
148952 KB |
Output is correct |
| 8 |
Correct |
9 ms |
148952 KB |
Output is correct |
| 9 |
Correct |
0 ms |
148952 KB |
Output is correct |
| 10 |
Correct |
3 ms |
148952 KB |
Output is correct |
| 11 |
Correct |
6 ms |
148952 KB |
Output is correct |
| 12 |
Correct |
33 ms |
152108 KB |
Output is correct |
| 13 |
Correct |
79 ms |
152108 KB |
Output is correct |
| 14 |
Correct |
56 ms |
152108 KB |
Output is correct |
| 15 |
Correct |
46 ms |
150572 KB |
Output is correct |
| 16 |
Correct |
49 ms |
152108 KB |
Output is correct |
| 17 |
Correct |
69 ms |
152108 KB |
Output is correct |
| 18 |
Correct |
53 ms |
152108 KB |
Output is correct |
| 19 |
Correct |
63 ms |
152108 KB |
Output is correct |
| 20 |
Correct |
49 ms |
152108 KB |
Output is correct |
| 21 |
Correct |
63 ms |
152108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
148952 KB |
Output is correct |
| 2 |
Correct |
6 ms |
148952 KB |
Output is correct |
| 3 |
Correct |
9 ms |
148952 KB |
Output is correct |
| 4 |
Incorrect |
23 ms |
148952 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
148952 KB |
Output is correct |
| 2 |
Correct |
9 ms |
148952 KB |
Output is correct |
| 3 |
Correct |
9 ms |
148952 KB |
Output is correct |
| 4 |
Incorrect |
13 ms |
148952 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
148952 KB |
Output is correct |
| 2 |
Correct |
3 ms |
148952 KB |
Output is correct |
| 3 |
Correct |
9 ms |
148952 KB |
Output is correct |
| 4 |
Incorrect |
19 ms |
148952 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
