#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 5003;
const int MAXM = 203;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
int N, M;
int H[MAXN][MAXM], V[MAXN][MAXM];
struct node {
int path[MAXM][MAXM];
int* operator[] (int x) {
return path[x];
}
};
int opt[MAXN][MAXM];
node operator + (const node &a, const node &b) {
node res;
fillchar(res.path, 63);
//opt[i - 1][j] <= opt[i][j] <= opt[i][j + 1]
//this is the KEY OBSERVATION
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
if (res[0][i] > a[0][j] + b[j][i]) {
res[0][i] = a[0][j] + b[j][i];
opt[0][i] = j;
}
}
}
//ok now let's do this
for (int i = 1; i < M; i++) {
//res[i][j] compute
//opt[i - 1][j] <= opt[i][j] <= opt[i][j + 1]
//for this reason it is better to do it in decreasing j
opt[i][M] = M - 1;
for (int j = M - 1; j >= 0; j--) {
for (int k = opt[i - 1][j]; k <= opt[i][j + 1]; k++) {
if (res[i][j] > a[i][k] + b[k][j]) {
res[i][j] = a[i][k] + b[k][j];
opt[i][j] = k;
}
}
}
}
return res;
}
struct segtree {
//so after all we need 512 * 2 = 1024
node tree[1 << 10];
node tmp[10];
void make (int cur, int a, int b) {
for (int r = a; r < b; r++) {
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
tmp[r - a][i][j] = V[r][j] + abs(H[r][i] - H[r][j]);
}
}
}
tree[cur] = tmp[0];
for (int i = 1; i < b - a; i++) {
tree[cur] = tree[cur] + tmp[i];
}
}
void update (int r, int cur, int lt, int rt) {
if (rt - lt <= 10) {
make(cur, lt, rt);
return;
}
int mid = (lt + rt) / 2;
if (r < mid) {
update(r, 2 * cur, lt, mid);
} else {
update(r, 2 * cur + 1, mid, rt);
}
tree[cur] = tree[2 * cur] + tree[2 * cur + 1];
}
void init (int cur, int lt, int rt) {
if (rt - lt <= 10) {
make(cur, lt, rt);
return;
}
int mid = (lt + rt) / 2;
init(2 * cur, lt, mid);
init(2 * cur + 1, mid, rt);
tree[cur] = tree[2 * cur] + tree[2 * cur + 1];
}
} seg;
void init (int nnn, int mmm, int hhh[5000][200], int vvv[5000][200]) {
N = nnn;
M = mmm;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M - 1; j++) {
H[i][j + 1] = H[i][j] + hhh[i][j];
}
}
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < M; j++) {
V[i][j] = vvv[i][j];
}
}
//optimal paths never cross over each other!
//KEY OBSERVATION!!!!
seg.init(1, 0, N);
}
void changeH (int x, int y, int w) {
int diff = w - (H[x][y + 1] - H[x][y]);
for (int i = y + 1; i < M; i++) {
H[x][i] += diff;
}
seg.update(x, 1, 0, N);
}
void changeV (int x, int y, int w) {
V[x][y] = w;
seg.update(x, 1, 0, N);
}
int escape (int v1, int v2) {
return seg.tree[1][v1][v2];
}
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
wombats.cpp: In function 'node operator+(const node&, const node&)':
wombats.cpp:39:23: error: passing 'const node' as 'this' argument discards qualifiers [-fpermissive]
if (res[0][i] > a[0][j] + b[j][i]) {
^
wombats.cpp:23:7: note: in call to 'int* node::operator[](int)'
int* operator[] (int x) {
^~~~~~~~
wombats.cpp:39:33: error: passing 'const node' as 'this' argument discards qualifiers [-fpermissive]
if (res[0][i] > a[0][j] + b[j][i]) {
^
wombats.cpp:23:7: note: in call to 'int* node::operator[](int)'
int* operator[] (int x) {
^~~~~~~~
wombats.cpp:40:20: error: passing 'const node' as 'this' argument discards qualifiers [-fpermissive]
res[0][i] = a[0][j] + b[j][i];
^
wombats.cpp:23:7: note: in call to 'int* node::operator[](int)'
int* operator[] (int x) {
^~~~~~~~
wombats.cpp:40:30: error: passing 'const node' as 'this' argument discards qualifiers [-fpermissive]
res[0][i] = a[0][j] + b[j][i];
^
wombats.cpp:23:7: note: in call to 'int* node::operator[](int)'
int* operator[] (int x) {
^~~~~~~~
wombats.cpp:54:24: error: passing 'const node' as 'this' argument discards qualifiers [-fpermissive]
if (res[i][j] > a[i][k] + b[k][j]) {
^
wombats.cpp:23:7: note: in call to 'int* node::operator[](int)'
int* operator[] (int x) {
^~~~~~~~
wombats.cpp:54:34: error: passing 'const node' as 'this' argument discards qualifiers [-fpermissive]
if (res[i][j] > a[i][k] + b[k][j]) {
^
wombats.cpp:23:7: note: in call to 'int* node::operator[](int)'
int* operator[] (int x) {
^~~~~~~~
wombats.cpp:55:21: error: passing 'const node' as 'this' argument discards qualifiers [-fpermissive]
res[i][j] = a[i][k] + b[k][j];
^
wombats.cpp:23:7: note: in call to 'int* node::operator[](int)'
int* operator[] (int x) {
^~~~~~~~
wombats.cpp:55:31: error: passing 'const node' as 'this' argument discards qualifiers [-fpermissive]
res[i][j] = a[i][k] + b[k][j];
^
wombats.cpp:23:7: note: in call to 'int* node::operator[](int)'
int* operator[] (int x) {
^~~~~~~~
