Submission #1242841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242841		Double_Slash	Wombats (IOI13_wombats)	C++20	100 / 100	2914 ms	177972 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9, SQRT = 10;
int R, C, n, H[5000][200], V[5000][200];

struct Node {
    int agg[200][200];
    Node *lc, *rc;

    void pull(int i) {
        memset(agg, 0x3f, sizeof agg);
        int dp[C];
        for (int c1 = C; c1--;) {
            agg[c1][c1] = 0;
            for (int r = i * SQRT; r <= min((i + 1) * SQRT, R - 1); ++r) {
                if (r > i * SQRT) {
                    for (int c2 = C; c2--;) agg[c1][c2] += V[r - 1][c2];
                }
                for (int c2 = C; --c2;) agg[c1][c2 - 1] = min(agg[c1][c2 - 1], agg[c1][c2] + H[r][c2 - 1]);
                for (int c2 = 0; ++c2 < C;) agg[c1][c2] = min(agg[c1][c2], agg[c1][c2 - 1] + H[r][c2 - 1]);
            }
        }
    }

    void pull() {
        int opt[C][C]{};
        for (int i = C; i--;) {
            int *o = &opt[i][i];
            for (int j = 0; ++j < C;) {
                if (lc->agg[i][j] + rc->agg[j][i] < lc->agg[i][*o] + rc->agg[*o][i]) *o = j;
            }
            agg[i][i] = lc->agg[i][*o] + rc->agg[*o][i];
            for (int j = i; ++j < C;) {
                o = &opt[i][j];
                for (int k = *o = opt[i][j - 1]; ++k <= opt[i + 1][j];) {
                    if (lc->agg[i][k] + rc->agg[k][j] < lc->agg[i][*o] + rc->agg[*o][j]) *o = k;
                }
                agg[i][j] = lc->agg[i][*o] + rc->agg[*o][j];
                o = &opt[j][i];
                for (int k = *o = opt[j - 1][i]; ++k <= opt[j][i + 1];) {
                    if (lc->agg[j][k] + rc->agg[k][i] < lc->agg[j][*o] + rc->agg[*o][i]) *o = k;
                }
                agg[j][i] = lc->agg[j][*o] + rc->agg[*o][i];
            }
        }
    }

    Node(int l, int r) {
        if (l < r) {
            int m = (l + r) >> 1;
            lc = new Node{l, m};
            rc = new Node{m + 1, r};
            pull();
        } else pull(l);
    }

    void upd(int i, int l, int r) {
        if (l == r) {
            pull(l);
            return;
        }
        int m = (l + r) >> 1;
        if (i <= m) lc->upd(i, l, m);
        else rc->upd(i, m + 1, r);
        pull();
    }
} *root;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = ((::R = R) - 2) / SQRT, ::C = C;
    memcpy(::H, H, sizeof ::H);
    memcpy(::V, V, sizeof ::V);
    root = new Node{0, n};
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    if (P) root->upd((P - 1) / SQRT, 0, n);
    if (P % SQRT == 0 and P < R) root->upd(P / SQRT, 0, n);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    root->upd(P / SQRT, 0, n);
}

int escape(int V1, int V2) { return root->agg[V1][V2]; }

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24