#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
/* Use segment tree, each node all C * C answers of interval l...r.
For query, it can be answered in O(1) by querying the root, V1 and V2
To merge, done naively is O(C * C * C). However, observe that we can
apply Knuth's optimization to make it O(C * C): observe that the grids
are planar, thus if will always follow the requirements for Knuth's optimization.
Also, O(R * C * C) memory is too large, thus we can decompose the grid into
blocks of a certain size, then build a segment tree of those blocks. To update
a block, just brute force it.
*/
int R, C;
vector<vector<int>> H, V;
const int BLOCK_SIZE = 20;
int BLOCK_COUNT;
struct segment_tree {
struct node {
vector<vector<int>> paths;
node(bool upd = false, int block = 0) {
paths.assign(C, vector<int>(C, INT_MAX));
if (!upd) return;
for (int i = 0; i < C; i++) {
paths[i][i] = 0;
for (int k = block * BLOCK_SIZE; k < (block + 1) * BLOCK_SIZE; k++) {
if (k >= R) continue;
for (int j = 1; j < C; j++) {
if (paths[i][j - 1] == INT_MAX) continue;
paths[i][j] = min(paths[i][j], paths[i][j - 1] + H[k][j - 1]);
}
for (int j = C - 2; j >= 0; j--) {
if (paths[i][j + 1] == INT_MAX) continue;
paths[i][j] = min(paths[i][j], paths[i][j + 1] + H[k][j]);
}
for (int j = 0; k < R - 1 && j < C; j++) {
paths[i][j] += V[k][j];
}
}
}
}
node merge(node a, node b) {
node res;
vector<vector<int>> mid(C, vector<int>(C, 0));
for (int len = 0; len < C; len++) {
for (int i = 0; i + len < C; i++) {
int j = i + len;
res.paths[i][j] = INT_MAX;
if (len == 0) {
for (int k = 0; k < C; k++) {
if (res.paths[i][j] > a.paths[i][k] + b.paths[k][j]) {
mid[i][j] = k;
res.paths[i][j] = a.paths[i][k] + b.paths[k][j];
}
}
continue;
}
/* DP Knuth's optimization, computing paths for new interval */
int le = mid[i][j - 1], ri = mid[i + 1][j];
for (int k = le; k <= ri; k++) {
if (res.paths[i][j] > a.paths[i][k] + b.paths[k][j]) {
mid[i][j] = k;
res.paths[i][j] = a.paths[i][k] + b.paths[k][j];
}
}
}
}
return res;
}
};
vector<node> tree;
inline int query(int v1, int v2) {
return tree[1].paths[v1][v2];
}
void update(int n, int tl, int tr, int p) {
if (tl == tr) {
tree[n] = node(true, tl);
return;
}
int mid = (tl + tr) / 2;
if (p <= mid)
update(n * 2, tl, mid, p);
else
update(n * 2 + 1, mid + 1, tr, p);
tree[n] = tree[n].merge(tree[n * 2], tree[n * 2 + 1]);
}
void build(int n, int tl, int tr) {
if (tl == tr) {
tree[n] = node(true, tl);
return;
}
int mid = (tl + tr) / 2;
build(n * 2, tl, mid), build(n * 2 + 1, mid + 1, tr);
tree[n] = tree[n].merge(tree[n * 2], tree[n * 2 + 1]);
}
void init() {
tree.clear();
tree.resize(4 * BLOCK_COUNT);
build(1, 0, BLOCK_COUNT - 1);
}
} seg;
void init(int R, int C, int h[5000][200], int v[5000][200]) {
::R = R, ::C = C;
H.assign(R, vector<int>(C - 1, 0));
V.assign(R - 1, 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];
}
}
BLOCK_COUNT = (R / BLOCK_SIZE) + 1;
seg.init();
}
void changeH(int P, int Q, int W) {
H[P][Q] = W;
seg.update(1, 0, BLOCK_COUNT - 1, P / BLOCK_SIZE);
}
void changeV(int P, int Q, int W) {
V[P][Q] = W;
seg.update(1, 0, BLOCK_COUNT - 1, P / BLOCK_SIZE);
}
int escape(int V1, int V2) {
// cout << V1 << " " << V2 << " ";
return seg.query(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;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4728 KB |
Output is correct |
| 2 |
Correct |
9 ms |
4728 KB |
Output is correct |
| 3 |
Correct |
82 ms |
7544 KB |
Output is correct |
| 4 |
Correct |
10 ms |
4772 KB |
Output is correct |
| 5 |
Correct |
10 ms |
4728 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
202 ms |
1656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
8828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
202 ms |
1656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
202 ms |
1648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
