| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 80726 | xiaowuc1 | 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>
/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/
using namespace std;
const double PI = 2 * acos(0);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, ll> pill;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<vector<ll>> matrix;
char buf1[5];
char buf2[5];
ll onesolve(vector<pii>& v, int x) {
ll ret = 0;
for(pii out: v) {
ret += abs(out.first-x) + abs(out.second-x);
}
return ret;
}
ll onesolve(vector<pii>& v) {
if(v.empty()) return 0;
vector<int> all;
for(auto out: v) {
all.push_back(out.first);
all.push_back(out.second);
}
sort(all.begin(), all.end());
return onesolve(v, all[all.size()/2]);
}
vector<int> allV;
class medianBIT {
vector<ll> sumbit;
vector<int> cntbit;
priority_queue<int> greaterQ;
priority_queue<int, vector<int>, greater<int>> lowerQ;
ll totalSum;
public:
ll query() {
if(totalSum == 0) return 0;
int med = greaterQ.top();
int idx = lower_bound(allV.begin(), allV.end(), med) - allV.begin();
pill x = _bit_query(idx);
ll rhssum = totalSum - x.second;
int rhsamt = greaterQ.size() + lowerQ.size() - x.first;
ll ans = (med * (ll)x.first - x.second) + (rhssum - med * (ll)rhsamt);
return ans;
}
void _rebalance() {
while(greaterQ.size() - lowerQ.size() > 1) {
lowerQ.push(greaterQ.top());
greaterQ.pop();
}
while(lowerQ.size() > greaterQ.size()) {
greaterQ.push(lowerQ.top());
lowerQ.pop();
}
if(lowerQ.empty()) return;
while(lowerQ.top() > greaterQ.top()) {
int lowlow = lowerQ.top();
int highhigh = greaterQ.top();
lowerQ.pop();
greaterQ.pop();
greaterQ.push(lowlow);
lowerQ.push(highhigh);
}
}
medianBIT() {
sumbit.resize(allV.size() + 2);
cntbit.resize(allV.size() + 2);
}
void _bit_update(int idx, int val) {
totalSum += val;
idx++;
while(idx < sumbit.size()) {
sumbit[idx] += val;
if(val > 0) cntbit[idx]++;
else cntbit[idx]--;
idx += idx & -idx;
}
}
pill _bit_query(int idx) {
idx++;
ll sumret = 0;
int cntret = 0;
while(idx) {
sumret += sumbit[idx];
cntret += cntbit[idx];
idx -= idx & -idx;
}
return {cntret, sumret};
}
void insert(int v) {
greaterQ.push(v);
int idx = lower_bound(allV.begin(), allV.end(), v) - allV.begin();
_bit_update(idx, v);
_rebalance();
}
void erase(int v) {
if(lower.count(v)) {
if(--lower[v] == 0) lower.erase(v);
lowersize--;
}
else {
assert(greater.count(v));
if(--greater[v] == 0) greater.erase(v);
greatersize--;
}
int idx = lower_bound(allV.begin(), allV.end(), v) - allV.begin();
_bit_update(idx, -v);
_rebalance();
}
};
bool piisort(pii a, pii b) {
return a.first + a.second < b.first + b.second;
}
ll twosolve(vector<pii>& v) {
if(v.empty()) return 0;
for(auto out: v) {
allV.push_back(out.first);
allV.push_back(out.second);
}
sort(allV.begin(), allV.end());
ll ret = onesolve(v, allV[allV.size()/2]);
medianBIT lhs;
medianBIT rhs;
sort(v.begin(), v.end(), piisort);
for(auto out: v) {
rhs.insert(out.first);
rhs.insert(out.second);
}
for(auto out: v) {
rhs.erase(out.first);
rhs.erase(out.second);
lhs.insert(out.first);
lhs.insert(out.second);
ret = min(ret, lhs.query() + rhs.query());
}
return ret;
}
int main() {
int k, n;
scanf("%d%d\n", &k, &n);
vector<pii> x;
ll inc = 0;
while(n--) {
int a, b;
scanf("%s %d %s %d\n", buf1, &a, buf2, &b);
a++;
b++;
if(buf1[0] == buf2[0]) {
inc += abs(b-a);
}
else {
x.push_back({min(a,b), max(a,b)});
}
}
if(k == 1) printf("%lld\n", onesolve(x) + inc + x.size());
else printf("%lld\n", twosolve(x) + inc + x.size());
}