| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1012579 | AmirAli_H1 | Wombats (IOI13_wombats) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// In the name of Allah
#include <bits/stdc++.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];
}