oj.uz

Submission #123085

# Submission time Handle Problem Language Result Execution time Memory
123085 2019-06-30T07:54:49 Z MAMBA Wombats (IOI13_wombats) C++17
100 / 100
 9264 ms 169816 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for (int i = j ; i < (int)k; i++)

inline bool smin(int &l, int r) {
	if (r < l) return l = r, true;
	return false;
}

inline bool smax(int &l ,int r) {
	if (l < r) return l = r , true;
	return false;
}

const int LEN = 35;
const int MAXN = 5000 / LEN + 10;

int R , C;
int dist[MAXN][2][202][202];
int H[5000][200];
int V[5000][200];

struct segment {
	int d[202][202];	
	segment() {
		memset(d , 63 , sizeof(d));
	}
} seg[MAXN << 2];

void solve(int So , int Z, const segment &L, const segment &R , segment &res, int l , int r, int s , int t) {
	if (l >= r) return;
	int mid = l + r >> 1;

	int best = s;
	int val = 1e9 + 10;

	rep(i , s , t + 1)
		if (smin(val , L.d[So][i] +  V[Z][i] + R.d[i][mid]))
			best = i;
	res.d[So][mid] = val;
	solve(So , Z , L , R , res , l , mid , s , best);
	solve(So , Z , L , R , res , mid + 1 , r , best , t);
}

inline void merge(segment &res , const segment &l, const segment &r, int mid) {
	rep(so , 0 , C) 
		solve(so, mid * LEN - 1 , l , r , res, 0 , C, 0 , C - 1);
}


void build(int l = 0, int r = (R - 1) / LEN + 1, int id = 1) {
//	cout << "LETS BUILD : " << l << ' ' << r << endl;
	if (l == r - 1) {
		rep(i , 0 , C)
			rep(j , 0 , C)
			seg[id].d[i][j] = dist[l][0][i][j];
		return;
	}
	int mid = l + r >> 1;
	build(l , mid , id << 1);
	build(mid , r ,id << 1 | 1);
	merge(seg[id] , seg[id << 1] ,  seg[id << 1 | 1] , mid);
}

void segUpt(int pos , int l = 0, int r = (R - 1) / LEN + 1, int id = 1) {
	if (l == r - 1) {
		rep(i , 0 , C)
			rep(j , 0 , C)
			seg[id].d[i][j] = dist[l][0][i][j];
		return;
	}
	int mid = l +r >> 1;
	if (pos < mid) segUpt(pos , l, mid , id << 1);
	else segUpt(pos , mid , r, id << 1 | 1);
	merge(seg[id] , seg[id << 1] ,  seg[id << 1 | 1] , mid);

}

inline void build_len(int id) {
	memset(dist[id] , 63 , sizeof(dist[id]));
	rep(i , 0 , C) {
		dist[id][0][i][i] = 0;
		rep(j , i + 1, C)
			dist[id][0][i][j] = dist[id][0][j][i] = dist[id][0][i][j - 1] + H[id * LEN][j - 1];
	}
	for (int i = id * LEN + 1; i < min(R , (id + 1) * LEN); i++) {
		memset(dist[id][1] , 63 , sizeof(dist[id][1]));
		rep(x , 0 , C) {
			for (int y = 0; y < C; y++) {
				smin(dist[id][1][x][y] , dist[id][0][x][y] + V[i - 1][y]);
				if (y)
					smin(dist[id][1][x][y] , dist[id][1][x][y - 1] + H[i][y - 1]);
			}
			for (int y = C - 1; ~y; y--) 
				if (y + 1 != C)
					smin(dist[id][1][x][y] , dist[id][1][x][y + 1] + H[i][y]);
		}
		/*
		rep(x , 0 , C)
			rep(y , 0 , C)
			cout << ' ' << x << ' '<< y << ' ' << dist[id][0][x][y] << endl;
		cout << endl;
		*/
		rep(x , 0 , C) rep(y , 0 , C) dist[id][0][x][y] = dist[id][1][x][y];
	}
	/*
	rep(x , 0 , C)
		rep(y , 0 , C)
		cout << ' ' << x << ' '<< y << ' ' << dist[id][0][x][y] << endl;
	*/
}

void init(int R_, int C_, int H_[5000][200], int V_[5000][200]) {
	R = R_ , C = C_;
	rep(i , 0 , R)
		rep(j , 0 , C - 1)
		H[i][j] = H_[i][j];
	rep(i , 0 , R - 1)
		rep(j , 0 , C)
		V[i][j] = V_[i][j];

	for (int i = 0; i * LEN  < R; i++)
		build_len(i);
	build();
}

void changeH(int P, int Q, int W) {
	H[P][Q] = W;
	build_len(P / LEN);
	segUpt(P / LEN);
}

void changeV(int P, int Q, int W) {
	V[P][Q] = W;
	build_len((P + 1) / LEN);
	segUpt(P / LEN);
}

int escape(int V1, int V2) {
	return seg[1].d[V1][V2];
}
/*
int main() {
	int r , c;
	cin >> r >> c;
	rep(i , 0 , r)
		rep(j , 0 , c - 1)
		cin >> H[i][j];
	rep(i , 0 , r - 1)
		rep(j , 0 , c)
		cin >> V[i][j];
	init(r , c , H , V);
	int e;
	cin >> e;
	while (e--) {
		int tp;
		cin >> tp;
		if (tp == 3) {
			int x , y;
			cin >> x >> y;
			cout << escape(x , y) << endl; 
		}
		else if (tp == 1) {
			int x , y , w;
			cin >> x >> y >> w;
			changeH(x ,y , w);
		}
		else {
			int x , y , w;
			cin >> x >> y >> w;
			changeV(x ,y , w);
		}
	}

	return 0;
}
*/

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 solve(int, int, const segment&, const segment&, segment&, int, int, int, int)':
wombats.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wombats.cpp: In function 'void build(int, int, int)':
wombats.cpp:62:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wombats.cpp: In function 'void segUpt(int, int, int, int)':
wombats.cpp:75:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l +r >> 1;
            ~~^~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 150904 KB Output is correct
2 Correct 324 ms 151052 KB Output is correct
3 Correct 391 ms 152544 KB Output is correct
4 Correct 326 ms 151020 KB Output is correct
5 Correct 316 ms 150876 KB Output is correct
6 Correct 79 ms 97784 KB Output is correct
7 Correct 79 ms 97816 KB Output is correct
8 Correct 79 ms 97720 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 97700 KB Output is correct
2 Correct 93 ms 97740 KB Output is correct
3 Correct 95 ms 97724 KB Output is correct
4 Correct 80 ms 97912 KB Output is correct
5 Correct 80 ms 97912 KB Output is correct
6 Correct 80 ms 97912 KB Output is correct
7 Correct 79 ms 97912 KB Output is correct
8 Correct 79 ms 97860 KB Output is correct
9 Correct 80 ms 97784 KB Output is correct
10 Correct 79 ms 97784 KB Output is correct
11 Correct 156 ms 98808 KB Output is correct
12 Correct 79 ms 97916 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 98808 KB Output is correct
2 Correct 311 ms 98920 KB Output is correct
3 Correct 356 ms 98776 KB Output is correct
4 Correct 338 ms 98808 KB Output is correct
5 Correct 320 ms 98808 KB Output is correct
6 Correct 82 ms 97912 KB Output is correct
7 Correct 79 ms 97784 KB Output is correct
8 Correct 79 ms 97724 KB Output is correct
9 Correct 1195 ms 98780 KB Output is correct
10 Correct 80 ms 97784 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 158816 KB Output is correct
2 Correct 356 ms 158968 KB Output is correct
3 Correct 336 ms 158856 KB Output is correct
4 Correct 374 ms 159608 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 98808 KB Output is correct
2 Correct 287 ms 98768 KB Output is correct
3 Correct 352 ms 98768 KB Output is correct
4 Correct 336 ms 98796 KB Output is correct
5 Correct 337 ms 98772 KB Output is correct
6 Correct 345 ms 158724 KB Output is correct
7 Correct 347 ms 158804 KB Output is correct
8 Correct 349 ms 158784 KB Output is correct
9 Correct 373 ms 159584 KB Output is correct
10 Correct 315 ms 150980 KB Output is correct
11 Correct 325 ms 150980 KB Output is correct
12 Correct 403 ms 152512 KB Output is correct
13 Correct 326 ms 150976 KB Output is correct
14 Correct 326 ms 150988 KB Output is correct
15 Correct 79 ms 97680 KB Output is correct
16 Correct 80 ms 97756 KB Output is correct
17 Correct 80 ms 97784 KB Output is correct
18 Correct 80 ms 97784 KB Output is correct
19 Correct 81 ms 97808 KB Output is correct
20 Correct 80 ms 97804 KB Output is correct
21 Correct 79 ms 97816 KB Output is correct
22 Correct 80 ms 97812 KB Output is correct
23 Correct 80 ms 97784 KB Output is correct
24 Correct 81 ms 97864 KB Output is correct
25 Correct 155 ms 98776 KB Output is correct
26 Correct 79 ms 97784 KB Output is correct
27 Correct 1194 ms 98772 KB Output is correct
28 Correct 2541 ms 159592 KB Output is correct
29 Correct 2429 ms 151636 KB Output is correct
30 Correct 2477 ms 151920 KB Output is correct
31 Correct 2474 ms 164692 KB Output is correct
32 Correct 80 ms 97756 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 98764 KB Output is correct
2 Correct 286 ms 98848 KB Output is correct
3 Correct 338 ms 98680 KB Output is correct
4 Correct 332 ms 98680 KB Output is correct
5 Correct 319 ms 98796 KB Output is correct
6 Correct 338 ms 158740 KB Output is correct
7 Correct 335 ms 158844 KB Output is correct
8 Correct 333 ms 158792 KB Output is correct
9 Correct 368 ms 159492 KB Output is correct
10 Correct 321 ms 151048 KB Output is correct
11 Correct 318 ms 151020 KB Output is correct
12 Correct 389 ms 152568 KB Output is correct
13 Correct 338 ms 151004 KB Output is correct
14 Correct 318 ms 151032 KB Output is correct
15 Correct 1281 ms 159012 KB Output is correct
16 Correct 9264 ms 169816 KB Output is correct
17 Correct 79 ms 97784 KB Output is correct
18 Correct 79 ms 97776 KB Output is correct
19 Correct 89 ms 97912 KB Output is correct
20 Correct 81 ms 97912 KB Output is correct
21 Correct 94 ms 97912 KB Output is correct
22 Correct 100 ms 97784 KB Output is correct
23 Correct 94 ms 97912 KB Output is correct
24 Correct 94 ms 97884 KB Output is correct
25 Correct 79 ms 97784 KB Output is correct
26 Correct 98 ms 97924 KB Output is correct
27 Correct 156 ms 100216 KB Output is correct
28 Correct 84 ms 97760 KB Output is correct
29 Correct 1189 ms 98852 KB Output is correct
30 Correct 2538 ms 163096 KB Output is correct
31 Correct 9175 ms 167416 KB Output is correct
32 Correct 9231 ms 167332 KB Output is correct
33 Correct 2433 ms 151680 KB Output is correct
34 Correct 8992 ms 155796 KB Output is correct
35 Correct 2472 ms 152024 KB Output is correct
36 Correct 8997 ms 156028 KB Output is correct
37 Correct 2460 ms 164836 KB Output is correct
38 Correct 8675 ms 167928 KB Output is correct
39 Correct 80 ms 97784 KB Output is correct
40 Correct 9126 ms 156136 KB Output is correct