Submission #505222

#	Time	Username	Problem	Language	Result	Execution time	Memory
505222		jhnah917	Wombats (IOI13_wombats)	C++14	100 / 100	6038 ms	229172 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

int n, m, q;
int h[5050][222];
int v[5050][222];

struct Node{
    Node *l, *r;
    int data[222][222];
    Node() : l(0), r(0) {
        memset(data, 0, sizeof data);
    }
};

void merge(int a[222][222], int b[222][222], int c[222][222]){ //a = b + c
    int K[222][222] = {0};
    for(int d=1-m; d<m; d++){
        for(int i=1; i<=m; i++){
            int j = i + d;
            if(j < 1 || j > m) continue;
            a[i][j] = 1e9+7;
            int l = K[i][j-1] ? K[i][j-1] : 1;
            int r = K[i+1][j] ? K[i+1][j] : m;
            for(int k=l; k<=r; k++){
                if(a[i][j] > b[i][k] + c[k][j]) a[i][j] = b[i][k] + c[k][j], K[i][j] = k;
            }
        }
    }
}

void small(int data[222][222], int s, int e){
    for(int i=1; i<=m; i++) for(int j=1; j<=m; j++) data[i][j] = 1e9+7;
    for(int i=1; i<=m; i++) data[i][i] = 0;
    int sum[222] = {0}, a[222][222] = {0}, b[222][222] = {0};
    for(int i=s; i<=e+1; i++){
        for(int j=1; j<=m; j++){
            for(int k=1; k<=m; k++){
                a[j][k] = data[j][k];
                if(i != s) a[j][k] += v[i-1][k];
            }
        }
        for(int j=2; j<=m; j++) sum[j] = sum[j-1] + h[i][j-1];
        for(int j=1; j<=m; j++){
            for(int k=j; k<=m; k++){
                b[j][k] = b[k][j] = sum[k] - sum[j];
            }
        }
        merge(data, a, b);
    }
}
Node* build(int s, int e){
    Node *ret = new Node();
    if(e-s < 15){
        small(ret->data, s, e);
        return ret;
    }
    int m = s + e >> 1;
    ret->l = build(s, m);
    ret->r = build(m+1, e);
    merge(ret->data, ret->l->data, ret->r->data);
    return ret;
}

void update(Node *node, int s, int e, int l, int r){
    if(r < s || e < l) return;
    if(e-s < 15){
        small(node->data, s, e);
        return;
    }
    int m = s + e >> 1;
    update(node->l, s, m, l, r);
    update(node->r, m+1, e, l, r);
    merge(node->data, node->l->data, node->r->data);
}

Node *root;
void init(int R, int C, int H[5000][200], int V[5000][200]){
    n = R; m = C;
    for(int i=1; i<=n; i++) for(int j=1; j<m; j++) h[i][j] = H[i-1][j-1];
    for(int i=1; i<n; i++) for(int j=1; j<=m; j++) v[i][j] = V[i-1][j-1];
    root = build(1, n-1);
}

void changeH(int i, int j, int k){
    i++; j++; h[i][j] = k;
    update(root, 1, n-1, i-1, i);
}

void changeV(int i, int j, int k){
    i++; j++; v[i][j] = k;
    update(root, 1, n-1, i, i);
}

int escape(int i, int j){
    i++; j++;
    return root->data[i][j];
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp: In function 'Node* build(int, int)':
wombats.cpp:59:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int m = s + e >> 1;
      |             ~~^~~
wombats.cpp: In function 'void update(Node*, int, int, int, int)':
wombats.cpp:72:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     int m = s + e >> 1;
      |             ~~^~~

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