oj.uz

Submission #1012587

# Submission time Handle Problem Language Result Execution time Memory
1012587 2024-07-02T11:08:31 Z AmirAli_H1 Wombats (IOI13_wombats) C++17
100 / 100
 8360 ms 199768 KB 
// In the name of Allah
 
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
 
typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;
 
#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int maxn = 5000 + 4;
const int maxs = (1 << 10) + 4;
const int maxm = 200 + 4, maxr = 23;
const int oo = 1e9 + 7;
 
int n, m, sz;
int A[maxn][maxm], B[maxn][maxm], sm[maxn][maxm];
int t[maxs][maxm][maxm], res[maxr][maxm][maxm];
int opt[maxm];
 
void get_opt(int l, int r, int lx, int rx, int v, int u1, int u2, int i1) {
	if (r - l <= 0) return ;
	int i2 = (l + r) / 2;
	int val = oo; opt[i2] = -1;
	for (int j = lx; j < rx; j++) {
		int x = res[u1][i1][j] + res[u2][j][i2];
		if (x < val) {
			val = x; opt[i2] = j;
		}
	}
	get_opt(l, i2, lx, opt[i2] + 1, v, u1, u2, i1);
	get_opt(i2 + 1, r, opt[i2], rx, v, u1, u2, i1);
}
 
void get_res(int v, int u1, int u2, int mid) {
	for (int i1 = 0; i1 < m; i1++) {
		for (int i2 = 0; i2 < m; i2++) {
			res[u1][i1][i2] += B[mid - 1][i2];
		}
	}
	for (int i1 = 0; i1 < m; i1++) {
		get_opt(0, m, 0, m, v, u1, u2, i1);
		for (int i2 = 0; i2 < m; i2++) {
			int j = opt[i2];
			res[v][i1][i2] = res[u1][i1][j] + res[u2][j][i2];
		}
	}
}
 
int calx(int l, int r) {
	int v = sz++;
	if (r - l == 1) {
		for (int i1 = 0; i1 < m; i1++) {
			for (int i2 = 0; i2 < m; i2++) {
				int lx = min(i1, i2), rx = max(i1, i2);
				res[v][i1][i2] = (sm[l][rx] - sm[l][lx]);
			}
		}
	}
	else {
		int mid = (l + r) / 2;
		int u1 = calx(l, mid), u2 = calx(mid, r);
		get_res(v, u1, u2, mid);
	}
	return v;
}
 
void f(int v, int mid) {
	int r = 0, u1 = 1, u2 = 2;
	for (int i1 = 0; i1 < m; i1++) {
		for (int i2 = 0; i2 < m; i2++) {
			res[u1][i1][i2] = t[2 * v + 1][i1][i2];
			res[u2][i1][i2] = t[2 * v + 2][i1][i2];
		}
	}
	get_res(r, u1, u2, mid);
	for (int i1 = 0; i1 < m; i1++) {
		for (int i2 = 0; i2 < m; i2++) {
			t[v][i1][i2] = res[r][i1][i2];
		}
	}
}
 
void build(int v, int tl, int tr) {
	if (tr - tl == 1 || 2 * v + 2 >= maxs) {
		sz = 0; int u = calx(tl, tr);
		for (int i1 = 0; i1 < m; i1++) {
			for (int i2 = 0; i2 < m; i2++) t[v][i1][i2] = res[u][i1][i2];
		}
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	f(v, mid);
}
 
void upd(int v, int tl, int tr, int i) {
	if (i >= tr || i < tl) return ;
	if (tr - tl == 1 || 2 * v + 2 >= maxs) {
		sz = 0; int u = calx(tl, tr);
		for (int i1 = 0; i1 < m; i1++) {
			for (int i2 = 0; i2 < m; i2++) t[v][i1][i2] = res[u][i1][i2];
		}
		return ;
	}
	int mid = (tl + tr) / 2;
	upd(2 * v + 1, tl, mid, i); upd(2 * v + 2, mid, tr, i);
	f(v, mid);
}
 
void init(int R, int C, int H[5000][200], int V[5000][200]) {
	n = R; m = C;
	for (int i = 0; i < n; i++) {
		sm[i][0] = 0;
		for (int j = 0; j < m - 1; j++) {
			A[i][j] = H[i][j];
			sm[i][j + 1] = sm[i][j] + A[i][j];
		}
	}
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < m; j++) B[i][j] = V[i][j];
	}
	build(0, 0, n);
}
 
void changeH(int i, int j, int x) {
	A[i][j] = x; sm[i][0] = 0;
	for (int j = 0; j < m - 1; j++) {
		sm[i][j + 1] = sm[i][j] + A[i][j];
	}
	upd(0, 0, n, i);
}
 
void changeV(int i, int j, int x) {
	B[i][j] = x;
	upd(0, 0, n, i);
}
 
int escape(int i1, int i2) {
	return t[0][i1][i2];
}

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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16728 KB Output is correct
2 Correct 8 ms 16732 KB Output is correct
3 Correct 59 ms 19432 KB Output is correct
4 Correct 7 ms 16728 KB Output is correct
5 Correct 7 ms 16732 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1368 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1112 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 41 ms 3708 KB Output is correct
12 Correct 1 ms 1372 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 17548 KB Output is correct
2 Correct 97 ms 17500 KB Output is correct
3 Correct 111 ms 17640 KB Output is correct
4 Correct 118 ms 17744 KB Output is correct
5 Correct 116 ms 17500 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 411 ms 17848 KB Output is correct
10 Correct 0 ms 344 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25436 KB Output is correct
2 Correct 12 ms 25436 KB Output is correct
3 Correct 13 ms 25684 KB Output is correct
4 Correct 31 ms 26960 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 17496 KB Output is correct
2 Correct 118 ms 17496 KB Output is correct
3 Correct 116 ms 17752 KB Output is correct
4 Correct 120 ms 17832 KB Output is correct
5 Correct 110 ms 17676 KB Output is correct
6 Correct 12 ms 25432 KB Output is correct
7 Correct 11 ms 25432 KB Output is correct
8 Correct 12 ms 25436 KB Output is correct
9 Correct 35 ms 26772 KB Output is correct
10 Correct 7 ms 16736 KB Output is correct
11 Correct 7 ms 16828 KB Output is correct
12 Correct 43 ms 19508 KB Output is correct
13 Correct 8 ms 16732 KB Output is correct
14 Correct 8 ms 16732 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 1164 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct
21 Correct 1 ms 1228 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 1 ms 1116 KB Output is correct
25 Correct 39 ms 3552 KB Output is correct
26 Correct 1 ms 1368 KB Output is correct
27 Correct 415 ms 17752 KB Output is correct
28 Correct 1700 ms 111608 KB Output is correct
29 Correct 1608 ms 107512 KB Output is correct
30 Correct 1802 ms 107608 KB Output is correct
31 Correct 1815 ms 113488 KB Output is correct
32 Correct 0 ms 348 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 17496 KB Output is correct
2 Correct 102 ms 17496 KB Output is correct
3 Correct 117 ms 17756 KB Output is correct
4 Correct 113 ms 17752 KB Output is correct
5 Correct 110 ms 17540 KB Output is correct
6 Correct 11 ms 25436 KB Output is correct
7 Correct 11 ms 25620 KB Output is correct
8 Correct 12 ms 25436 KB Output is correct
9 Correct 42 ms 26792 KB Output is correct
10 Correct 7 ms 16732 KB Output is correct
11 Correct 7 ms 16780 KB Output is correct
12 Correct 43 ms 19536 KB Output is correct
13 Correct 8 ms 16732 KB Output is correct
14 Correct 7 ms 16788 KB Output is correct
15 Correct 2710 ms 199428 KB Output is correct
16 Correct 7529 ms 199768 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 452 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct
21 Correct 1 ms 1372 KB Output is correct
22 Correct 1 ms 1372 KB Output is correct
23 Correct 1 ms 1372 KB Output is correct
24 Correct 1 ms 1116 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 1 ms 1368 KB Output is correct
27 Correct 43 ms 3740 KB Output is correct
28 Correct 1 ms 1224 KB Output is correct
29 Correct 484 ms 17800 KB Output is correct
30 Correct 1937 ms 111632 KB Output is correct
31 Correct 8360 ms 198968 KB Output is correct
32 Correct 7167 ms 198860 KB Output is correct
33 Correct 1687 ms 107580 KB Output is correct
34 Correct 6594 ms 194072 KB Output is correct
35 Correct 1761 ms 107724 KB Output is correct
36 Correct 6709 ms 194384 KB Output is correct
37 Correct 1762 ms 113408 KB Output is correct
38 Correct 7309 ms 199384 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 6593 ms 194248 KB Output is correct