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>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int inf = 1e9 + 5;
auto compare_frac = [](pii a, pii b) -> bool { return (ll)a.first * b.second < (ll)b.first * a.second; };
auto convoluted_cmpfrac = [](pair<pii,int> a, pair<pii,int> b) -> bool { return compare_frac(a.first, b.first); };
struct Turneu {
set<int> appears;
int *a;
set<pair<pii, int>, decltype(convoluted_cmpfrac)> heap;
Turneu(): heap(convoluted_cmpfrac) {;}
int n;
template<class iteratorlmao>
void insertIt(iteratorlmao it) {
if(*next(it) == n + 1 || *it == -1) return;
//cerr << *it << '\t' << a[*next(it)] << ' ' << a[*it] << '\n';
heap.emplace(pii{a[*next(it)] - a[*it], *next(it) - *it}, *it);
}
template<class iteratorlmao>
void eraseIt(iteratorlmao it) {
if(*next(it) == n + 1 || *it == -1) return;
heap.erase(heap.find(pair<pii,int>{pii{a[*next(it)] - a[*it], *next(it) - *it}, *it}));
}
void init(int _n, int *v) {
n = _n;
a = v;
appears.insert(-1);
appears.insert(n + 1);
for(int i = 1; i <= n; i++)
insertIt(prev(appears.insert(i).first));
heap.emplace(pii{inf, 0}, -1);
}
void erase(int p) {
assert(p > -1);
//cerr << "stergem " << p << "\n--\n";
auto it = appears.find(p);
eraseIt(it);
eraseIt(prev(it));
auto nvit = prev(it);
appears.erase(it);
insertIt(nvit);
}
};
const int nmax = 1e5 + 5;
int A[nmax], B[nmax];
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int H, W;
cin >> H >> W;
for(int i = 1; i <= H; i++) cin >> A[i];
for(int i = 1; i <= W; i++) cin >> B[i];
Turneu linii, coloane;
linii.init(H, A);
coloane.init(W, B);
ll cost = 0;
int x = 1, y = 1;
auto move_col = [&]() {
int nvy = *next(coloane.appears.begin());
cost += (ll)(nvy - y) * A[x];
y = nvy;
};
auto move_row = [&]() {
int nvx = *next(linii.appears.begin());
cost += (ll)(nvx - x) * B[y];
x = nvx;
};
while(x != H || y != W) {
//auto [Ax, Ay] = linii.heap.begin() -> first;
//auto [Bx, By] = coloane.heap.begin() -> first;
//cerr << Ax << "/" << Ay << '\t' << Bx << "/" << By << '\n';
if(compare_frac(linii.heap.begin() -> first, coloane.heap.begin() -> first))
cerr << "1\n",
linii.erase(linii.heap.begin() -> second);
else
cerr << "2\n",
coloane.erase(coloane.heap.begin() -> second);
move_col(); // gen, merge sa le fac pe ambele albeit e retardat
move_row();
}
cout << cost << '\n';
}
/**
Anul asta nu se da centroid
-- Rugaciunile mele
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |