IOI 2013 Wombats (55/100)

HOJ289.cpp

#include <cstdio>
#include <limits>
#include <algorithm>
using namespace std;

constexpr int max_r = 5000;
constexpr int max_c =  100;

int r, c;
int h[max_r][max_c - 1];
int v[max_r - 1][max_c];

int data[2550000];
struct Data {
    struct A {
        struct B {
            int b;
            B(int bb) : b(bb) {}
            int& operator [] (int x) { return data[b * c + x]; }
        };

        int a;
        A(int aa) : a(aa) {}
        B operator [] (int b) { return B(a * c + b); }
    };

    A operator [] (int a) { return A(a); }
} t;

void re_initialize(int n, int kk) {
    for(int i = 0; i < c; i++)
        for(int j = 0; j < c; j++)
            t[kk][i][j] = accumulate(h[n] + min(i, j), h[n] + max(i, j), 0);
}

void re_merge(int n, int kk) {
    for(int i = 0; i < c; i++)
        for(int j = 0; j < c; j++) {
            t[kk][i][j] = numeric_limits<int>::max();
            for(int k = 0; k < c; k++)
                t[kk][i][j] = min(t[kk][i][j], t[2 * kk + 1][i][k] + v[n][k] + t[2 * kk + 2][k][j]);
        }
}

void initialize(int nl = 0, int nr = r, int kk = 0) {
    if(nl + 1 == nr) {
        re_initialize(nl, kk);
    } else {
        initialize(nl, (nl + nr) / 2, 2 * kk + 1);
        initialize((nl + nr) / 2, nr, 2 * kk + 2);
        re_merge((nl + nr) / 2 - 1, kk);
    }
}

void modify_h(int p, int q, int nl = 0, int nr = r, int kk = 0) {
    if(nl + 1 == nr) {
        re_initialize(nl, kk);
    } else {
        if(p < (nl + nr) / 2)
            modify_h(p, q, nl, (nl + nr) / 2, 2 * kk + 1);
        else
            modify_h(p, q, (nl + nr) / 2, nr, 2 * kk + 2);
        re_merge((nl + nr) / 2 - 1, kk);
    }
}

void modify_v(int p, int q, int nl = 0, int nr = r, int kk = 0) {
    if(p < (nl + nr) / 2 - 1)
        modify_v(p, q, nl, (nl + nr) / 2, 2 * kk + 1);
    else if(p > (nl + nr) / 2 - 1)
        modify_v(p, q, (nl + nr) / 2, nr, 2 * kk + 2);
    re_merge((nl + nr) / 2 - 1, kk);
}

int query(int v1, int v2) {
    return t[0][v1][v2];
}

int main(){
    scanf("%d %d", &r, &c);
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c - 1; j++)
            scanf("%d", h[i] + j);
    for(int i = 0; i < r - 1; i++)
        for(int j = 0; j < c; j++)
            scanf("%d", v[i] + j);
    initialize();
    int e;
    scanf("%d", &e);
    while(e--) {
        int x;
        scanf("%d", &x);
        switch(x) {
        case 1: {
            int p, q, w;
            scanf("%d %d %d", &p, &q, &w);
            h[p][q] = w;
            modify_h(p, q);
            break;
        }
        case 2: {
            int p, q, w;
            scanf("%d %d %d", &p, &q, &w);
            v[p][q] = w;
            modify_v(p, q);
            break;
        }
        case 3: {
            int v1, v2;
            scanf("%d %d", &v1, &v2);
            printf("%d\n", query(v1, v2));
            break;
        }
        }
    }
}