#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<int> > Paths;
const int MAXD = 100000000; // 1e8
int r;
int c;
vector<vector<int> > h;
vector<vector<int> > v;
void pr(const Paths &ans){
for(int i = 0; i < c; i++){
for(int j = 0; j < c; j++){
cout << ans[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void dnc(const Paths &a, const Paths &b, Paths &paths, int t, int bl, int br, int ml, int mr){
if(bl > br) return;
// top, bottom left, bottom right
int bm = (bl + br) / 2;
int best = MAXD + 1;
int bestm = -1;
for(int m = ml; m <= mr; m++){
int dist = a[t][m] + b[m][bm];
if(dist < best){
best = dist;
bestm = m;
}
}
assert(bestm != -1);
paths[t][bm] = best;
dnc(a, b, paths, t, bl, bm - 1, ml, bestm);
dnc(a, b, paths, t, bm + 1, br, bestm, mr);
}
Paths join(const Paths &a, const Paths &b){
Paths paths(c, vector<int>(c, MAXD));
for(int i = 0; i < c; i++){
dnc(a, b, paths, i, 0, c-1, 0, c-1);
}
return paths;
}
Paths horizontal(int row){
vector<int> psums(c);
psums[0] = 0;
for(int i = 1; i < c; i++){
psums[i] = psums[i-1] + h[row][i-1];
}
Paths paths(c, vector<int>(c, MAXD));
for(int i = 0; i < c; i++){
for(int j = 0; j < c; j++){
paths[i][j] = abs(psums[j] - psums[i]);
}
}
return paths;
}
Paths empty(){
Paths p2(c, vector<int>(c, MAXD));
for(int i = 0; i < c; i++){
p2[i][i] = 0;
}
return p2;
}
Paths make(int row){
Paths p2(c, vector<int>(c, MAXD));
for(int i = 0; i < c; i++){
p2[i][i] = v[row][i];
}
return join(horizontal(row), p2);
}
Paths make_interval(int r1, int r2){
Paths p = make(r1);
for(int a = r1 + 1; a <= r2; a++){
p = join(p, make(a));
}
return p;
}
Paths ans;
struct node {
Paths p;
node *l, *r;
int lx, rx;
};
const int BLOCKSZ = 15;
node* build(int lx, int rx){
node* v = new node();
v->lx = lx;
v->rx = rx;
if(rx - lx + 1 <= BLOCKSZ){
v->l = v->r = NULL;
v->p = make_interval(v->lx, v->rx);
} else {
int mx = (lx + rx) / 2;
v->l = build(lx, mx);
v->r = build(mx + 1, rx);
v->p = join(v->l->p, v->r->p);
}
return v;
}
void upd(node* v, int x){
if(x < v->lx || x > v->rx) return;
if(v->l == NULL && v->r == NULL){
v->p = make_interval(v->lx, v->rx);
} else {
upd(v->l, x);
upd(v->r, x);
v->p = join(v->l->p, v->r->p);
}
}
node* tree;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r = R;
c = C;
h.resize(r, vector<int>(c-1, 0));
v.resize(r, vector<int>(c, 0));
for(int i = 0; i < r; i++){
for(int j = 0; j < c-1; j++){
h[i][j] = H[i][j];
}
}
for(int i = 0; i < r-1; i++){
for(int j = 0; j < c; j++){
v[i][j] = V[i][j];
}
}
tree = build(0, r-1);
}
void changeH(int P, int Q, int W) {
h[P][Q] = W;
upd(tree, P-1);
upd(tree, P);
}
void changeV(int P, int Q, int W) {
v[P][Q] = W;
upd(tree, P);
}
int escape(int V1, int V2) {
return tree->p[V1][V2];
}
