#include "wombats.h"
#include <bits/stdc++.h>
#define R 5000
#define C 200
using namespace std;
const int block = 15;
int r,c;
int h[R][C];
int w[R][C];
int opt[C][C];
struct node{
int a[C][C];
int l,r;
node(int init){
for(int i = 0;i<C;i++){
for(int j = 0;j<C;j++){
a[i][j] = init;
}
}
}
};
node merge(node a,node b){
node ret(1e9);
for(int dif = -c-1;dif < c ;dif++){
for(int i = max(0,-dif);i + dif<c;i++){
int j = dif + i;
int l = 0,r = c-1;
if(j)
l = opt[i][j-1];
if(i + 1 != c)
r = opt[i+1][j];
for(int x = l;x<=r;x++){
if(a.a[i][x] + b.a[x][j] < ret.a[i][j]){
ret.a[i][j] = a.a[i][x] + b.a[x][j];
opt[i][j] = x;
}
}
}
}
return ret;
}
struct SegTree{
vector<node> t;
int n;
void init(int size){
n = size;
t.assign(4*n,1e9);
build(1,0,n-1);
}
void build(int v,int tl,int tr){
t[v].l = tl * block;
t[v].r = min(r-1,(tr + 1) * block - 1);
if(tl == tr){
for(int i = 0;i<c;i++){
t[v].a[i][i] = 0;
for(int j = t[v].l;j<=t[v].r;j++){
for(int d=1;d<c;d++){
t[v].a[i][d] = min(t[v].a[i][d],t[v].a[i][d-1] + h[j][d-1]);
}
for(int d=c-2;d>=0;d--){
t[v].a[i][d] = min(t[v].a[i][d],t[v].a[i][d+1] + h[j][d]);
}
if(j != t[v].r){
for(int d=0;d<c;d++){
t[v].a[i][d] = t[v].a[i][d] + w[j][d];
}
}
}
}
return;
}
int tm = (tl + tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
t[v] = merge(t[v*2],t[v*2+1]);
}
void upd(int v,int tl,int tr,int pos){
t[v].l = tl * block;
t[v].r = min(r-1,(tr + 1) * block - 1);
if(tl == tr){
for(int i = 0;i<c;i++){
t[v].a[i][i] = 0;
for(int j = t[v].l;j<=t[v].r;j++){
for(int d=1;d<c;d++){
t[v].a[i][d] = min(t[v].a[i][d],t[v].a[i][d-1] + h[j][d-1]);
}
for(int d=c-2;d>=0;d--){
t[v].a[i][d] = min(t[v].a[i][d],t[v].a[i][d+1] + h[j][d]);
}
for(int d=0;d<c;d++){
t[v].a[i][d] = t[v].a[i][d] + w[j][d];
}
}
}
return;
}
int tm = (tl + tr)/2;
if(pos <= tm)
upd(v*2,tl,tm,pos);
else upd(v*2+1,tm+1,tr,pos);
t[v] = merge(t[v*2],t[v*2+1]);
}
void upd(int pos){
upd(1,0,n-1,pos);
}
}tree;
void init(int r_, int c_, int h_[5000][200], int v_[5000][200]) {
r = r_;
c = c_;
for(int i = 0;i<r;i++){
for(int j = 0;j<c;j++){
h[i][j] = h_[i][j];
w[i][j] = v_[i][j];
}
}
tree.init((r+block-1) / block);
}
void changeH(int p, int q, int x) {
h[p][q] = x;
tree.upd(p/block);
}
void changeV(int p, int q, int x) {
w[p][q] = x;
if(p % block == 0 && p)
tree.upd(p/block - 1);
tree.upd(p/block);
}
int escape(int v1, int v2) {
return tree.t[1].a[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]
15 | int res;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
266 ms |
222936 KB |
Output is correct |
| 2 |
Incorrect |
275 ms |
222812 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2132 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2132 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
2132 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
11548 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
267 ms |
226888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
11476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
11568 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
