#include "wombats.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define umax( x, y ) x = max( x, y )
#define umin( x, y ) x = min( x, y )
using namespace std;
const int maxn = 100000;
const int maxR = 5020;
const int maxC = 220;
typedef long long Lint;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
struct node {
int go[201][201];
int l, r;
};
node segment[1<<10];
vector<ii> v;
int n, c, r;
int R[5001][201];
int C[5001][201];
int opt[201][201];
void print( node t ) {
printf("------- %d %d\n",t.l,t.r);
for(int i=0;i<c;i++,printf("\n"))
for(int j=0;j<c;j++) printf("%d ",t.go[i][j]);
}
bool comp( const ii &a, const ii &b ) {
return a.se-a.fi < b.se-b.fi;
}
node merge( node a, node b ) {
if( !b.l && !b.r ) return a;
if( !a.l && !a.r ) return b;
node t;
t.l = a.l;
t.r = b.r;
for(int p=0;p<v.size();p++) {
int x = v[p].fi;
int y = v[p].se;
opt[x][y] = 0;
int val = 1e9;
int beg = 0, en = c-1;
if( x+1 < c ) umin( en, opt[x+1][y] );
if( y > 0 ) umax( beg, opt[x][y-1] );
while( beg <= en ) {
int h = a.go[x][beg]+R[a.r][beg]+b.go[beg][y];
if( h < val ) {
val = h;
opt[x][y] = beg;
}
beg++;
}
t.go[x][y] = val;
}
return t;
}
void relax( int x, int ar[] ) {
for(int i=c-2;i>=0;i--)
umin( ar[i], ar[i+1]+R[x][i] );
for(int i=1;i<c;i++)
umin( ar[i], ar[i-1]+R[x][i-1] );
}
void calc( int n ) {
node &t = segment[n];
for(int i=0;i<c;i++)
for(int j=0;j<c;j++)
t.go[i][j] = (i==j)? 0:1e9;
for(int i=0;i<c;i++) relax( t.l, t.go[i] );
//printf("-------- %d\n",n);
//print( t );
for(int k=t.l;k<t.r;k++) {
for(int i=0;i<c;i++)
for(int j=0;j<c;j++) t.go[i][j] += C[k][j];
//print( t );
for(int i=0;i<c;i++) relax( k+1, t.go[i] );
//print( t );
//printf("----------- %d\n",k+1);
}
}
void init(int rr, int cc, int RR[5000][200], int CC[5000][200]) {
r = rr;
c = cc;
for(int i=0;i<r;i++)
for(int j=0;j<c-1;j++)
R[i][j] = RR[i][j];
for(int i=0;i<r-1;i++)
for(int j=0;j<c;j++)
C[i][j] = CC[i][j];
n = 1;
while( n < (r-1)/10+1 ) n <<= 1;
for(int i=0;i*10<r;i++) {
segment[i+n].l = i*10;
segment[i+n].r = min( i*10+9, r-1 );
calc( i+n );
}
for(int i=n-1;i>0;i--)
segment[i] = merge( segment[i+i], segment[i+i+1] );
}
void changeH(int P, int Q, int W) {
R[P][Q] = W;
int k = P / 10 + n;
if( P%10 != 9 ) {
calc( k );
}
for(k>>=1;k;k>>=1)
segment[k] = merge( segment[k+k], segment[k+k+1] );
}
void changeV(int P, int Q, int W) {
C[P][Q] = W;
for(int k=(P/10+n)>>1;k;k>>=1) segment[k] = merge( segment[k+k], segment[k+k+1] );
}
int escape(int V1, int V2) {
return segment[1].go[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 merge(node, node)':
wombats.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int p=0;p<v.size();p++) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
299 ms |
179964 KB |
Output is correct |
| 2 |
Incorrect |
299 ms |
179968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
179496 KB |
Output is correct |
| 2 |
Correct |
0 ms |
179496 KB |
Output is correct |
| 3 |
Correct |
0 ms |
179492 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
179968 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
179968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
363 ms |
179964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
179964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
179964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
