| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 164364 |
2019-11-19T15:40:46 Z |
costle |
Wombats (IOI13_wombats) |
C++17 |
|
0 ms |
0 KB |
#include <stdio.h>
#include <algorithm>
#define INF 1e9
#define ele (1<<9)
#define R 5000
#define C 200
#define BS 10
#define BN R/BS
using namespace std;
int H[R][C-1],V[R][C];
int sgt[ele<<1][C][C],p[C+1];
void update_(int xs,int xe,int w,int l,int r){
if(l==r){
for(int i=0;i<C;i++){
for(int j=0;j<C;j++) sgt[w][i][j]=INF;
}
for(int i=0;i<C;i++){
sgt[w][i][i]=0;
for(int j=l*BS;j<(l+1)*BS;j++){
for(int k=1;k<C;k++) sgt[w][i][k]=min(sgt[w][i][k-1]+H[j][k-1],sgt[w][i][k]);
for(int k=C-1;k;k--) sgt[w][i][k-1]=min(sgt[w][i][k]+H[j][k-1],sgt[w][i][k-1]);
for(int k=0;k<C;k++) sgt[w][i][k]+=V[j][k];
}
}
return;
}
int m=(l+r)>>1;
if(xs<=m) update_(xs,xe,w<<1,l,m);
if(m<xe) update_(xs,xe,w<<1|1,m+1,r);
for(int i=0;i<C;i++) p[i]=0;
for(int i=0;i<C;i++){
for(int j=C-1;j;j--){
int mn=INF,mni=0;
for(int k=p[j];k<=p[j+1];k++){
if(mn>=sgt[w<<1][i][k]+sgt[w<<1|1][k][j]) mn=sgt[w<<1][i][k]+sgt[w<<1|1][k][j],mni=k;
}
sgt[w][i][j]=mn,p[j]=mni;
}
}
}
void init(int r, int c, int h[5000][200], int v[5000][200]) {
for(int i=0;i<R;i++){
for(int j=0;j<C-1;j++) H[i][j]=INF;
}
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];
}
p[C]=C-1;
update_(0,BN-1,1,0,BN-1);
}
void changeH(int a, int b, int c) {
H[a][b]=c;
update_(a/BS,a/BS,1,0,BN-1);
}
void changeV(int a, int b, int c) {
V[a][b]=c;
update_(a/BS,a/BS,1,0,BN-1);
}
int escape(int a, int b) {
return sgt[1][a][b];
}
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 'void update_(int, int, int, int, int)':
wombats.cpp:67:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
}
^
wombats.cpp:67:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:67:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:12:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
void update_(int xs,int xe,int w,int l,int r){
^~~~~~~
wombats.cpp:12:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:12:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
/tmp/ccZ7Wmdb.o: In function `main':
grader.c:(.text.startup+0x103): undefined reference to `init'
grader.c:(.text.startup+0x164): undefined reference to `escape'
grader.c:(.text.startup+0x1cf): undefined reference to `changeH'
grader.c:(.text.startup+0x23b): undefined reference to `changeV'
collect2: error: ld returned 1 exit status
