oj.uz

Submission #164365

# Submission time Handle Problem Language Result Execution time Memory
164365 2019-11-19T15:46:13 Z costle Wombats (IOI13_wombats) C++17
0 / 100
 3717 ms 172444 KB 
#include "wombats.h"

#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:69:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 }
 ^
wombats.cpp:69:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:69:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:14: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:14:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:14:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3717 ms 168832 KB Output is correct
2 Incorrect 3606 ms 168568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1392 ms 160824 KB Output is correct
2 Incorrect 1397 ms 160760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1852 ms 161220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 3673 ms 172444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1834 ms 161044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1879 ms 161140 KB Output isn't correct
2 Halted 0 ms 0 KB -