oj.uz

Submission #786815

# Submission time Handle Problem Language Result Execution time Memory
786815 2023-07-18T13:09:52 Z drdilyor Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 26204 KB 
#include<bits/stdc++.h>
#include "wombats.h"
#define int ll
using namespace std;
using ll = long long;
const int inf = 1e9;
constexpr ll infl = 1e18;

struct SegmentTree {
    using T = ll;
    using S = ll;
    const T id = infl;
    inline T single(S v) { return v; }

    T merge(const T& l, const T& r) {
        return min(l, r);
    }

    int n;
    vector<T> tree;

    SegmentTree(int n) : n(n) {
        tree.resize(n * 2, id);
        build();
    }
    SegmentTree(vector<S> arr) : n(arr.size()) {
        tree.resize(n * 2, id);
        for (int i = 0; i < n; i++) {
            tree[i + n] = single(arr[i]);
        }
        build();
    }

    void build() {
        for (int i = n-1; i >= 1; i--) {
            tree[i] = merge(tree[i*2], tree[i*2 + 1]);
        }
    }

    void update(int i, S v) {
        tree[i+=n] = single(v);
        for (i /= 2; i >= 1; i/= 2)
            tree[i] = merge(tree[i*2], tree[i*2+1]);
    }

    T query(int l, int r) {
        T left = id, right = id;
        l += n;
        r += n;
        while (l <= r) {
            if (l % 2 == 1) left = merge(left, tree[l++]);
            if (r % 2 == 0) right = merge(right, tree[r--]);
            l /= 2; r /= 2;
        }
        return merge(left, right);
    }

    int find_first(function<bool(T&)> predicate, int last = 0) {
        int v = 1;
        while (v < n) {
            if (predicate(tree[v*2 + last])) v = v*2 + last;
            else if (predicate(tree[v*2 + !last])) v = v*2 + !last;
            else return -1;
        }
        return v;
    }
};

struct Fenwick {
    int n;
    vector<ll> tree;

    Fenwick() = default;
    Fenwick(int n) : n(n) {
        tree.assign(n, 0);
    }

    void inc(int pos, ll val) {
        for (; pos < n; pos |= (pos + 1)) {
            tree[pos] += val;
        }
    }

    ll sum(int r) { // [0, r]
        ll ans = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) {
            ans += tree[r];
        }
        return ans;
    }

    ll sum(int l, int r) { // [l, r]
        return sum(r) - sum(l - 1);
    }

    int operator[](int index) {
        return sum(index) - sum(index-1);
    };
};

int r, c;
vector<Fenwick> level;
vector<Fenwick> pass;
vector<vector<ll>> dist;

vector<int> dirty;

void update(int v2) {
    if (!dirty[v2]) return;
    dirty[v2] = 0;

    vector<ll> dp(c, infl);
    dp[v2] = 0;
    SegmentTree st(c);
    for (int i = r-1; i >= 0; i--) {

        auto sum = [&](int r) {
            return level[i].sum(r);
        };

        vector<ll> ndp(dp);

        for (int j = 0; j < c; j++) {
            ll mn = st.query(0, j-1);
            ndp[j] = min(ndp[j], mn + sum(j-1));
            st.update(j, dp[j] - sum(j - 1));
        }

        for (int j = c-1; j >= 0; j--) {
            ll mn = st.query(j+1, c-1);
            ndp[j] = min(ndp[j], mn - sum(j-1));
            st.update(j, dp[j] + sum(j-1));
        }

        for (int j = 0; j < c; j++) {
            if (i) ndp[j] += pass[i-1][j];
        }

        dp.swap(ndp);
    }
    for (int v1 = 0; v1 < c; v1++)
        dist[v1][v2] = dp[v1];
}

void init(int32_t r, int32_t c, int32_t h[5000][200], int32_t v[5000][200]) {
    ::r = r;
    ::c = c;
    level.resize(r);
    for (int i = 0; i < r; i++) {
        level[i] = Fenwick(c);
        for (int j = 0; j < c-1; j++) {
            level[i].inc(j, h[i][j]);
        }
    }

    pass.resize(r-1);
    for (int i = 0; i < r-1; i++) {
        pass[i] = Fenwick(c);
        for (int j = 0; j < c; j++) {
            pass[i].inc(j, v[i][j]);
        }
    }
    dirty.assign(c, 1);
    dist = vector(c, vector(c, 0ll));
}

void changeH(int32_t p, int32_t q, int32_t w) {
    level[p].inc(q, w - level[p][q]);
    dirty.assign(c, 1);
}

void changeV(int32_t p, int32_t q, int32_t w) {
    pass[p].inc(q, w - pass[p][q]);
    dirty.assign(c, 1);
}

int32_t escape(int32_t v1, int32_t v2) {
    update(v2);
    return dist[v1][v2];
}

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 55 ms 4820 KB Output is correct
2 Correct 59 ms 4844 KB Output is correct
3 Correct 107 ms 7532 KB Output is correct
4 Correct 69 ms 4872 KB Output is correct
5 Correct 55 ms 4820 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 304 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 55 ms 1288 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 596 KB Output is correct
2 Correct 75 ms 768 KB Output is correct
3 Correct 70 ms 700 KB Output is correct
4 Correct 74 ms 780 KB Output is correct
5 Correct 70 ms 724 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 240 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 34 ms 724 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 8752 KB Output is correct
2 Correct 183 ms 8940 KB Output is correct
3 Correct 181 ms 8824 KB Output is correct
4 Correct 215 ms 10176 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 596 KB Output is correct
2 Correct 67 ms 768 KB Output is correct
3 Correct 70 ms 788 KB Output is correct
4 Correct 71 ms 784 KB Output is correct
5 Correct 72 ms 772 KB Output is correct
6 Correct 184 ms 8824 KB Output is correct
7 Correct 180 ms 8804 KB Output is correct
8 Correct 181 ms 8788 KB Output is correct
9 Correct 212 ms 10144 KB Output is correct
10 Correct 57 ms 4820 KB Output is correct
11 Correct 61 ms 4888 KB Output is correct
12 Correct 108 ms 7640 KB Output is correct
13 Correct 57 ms 4876 KB Output is correct
14 Correct 57 ms 4820 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 312 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 308 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 54 ms 2620 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 37 ms 724 KB Output is correct
28 Execution timed out 20053 ms 18068 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 700 KB Output is correct
2 Correct 70 ms 768 KB Output is correct
3 Correct 80 ms 784 KB Output is correct
4 Correct 70 ms 700 KB Output is correct
5 Correct 76 ms 724 KB Output is correct
6 Correct 183 ms 8828 KB Output is correct
7 Correct 188 ms 8804 KB Output is correct
8 Correct 218 ms 8832 KB Output is correct
9 Correct 221 ms 10200 KB Output is correct
10 Correct 72 ms 4864 KB Output is correct
11 Correct 67 ms 4880 KB Output is correct
12 Correct 119 ms 7640 KB Output is correct
13 Correct 60 ms 4820 KB Output is correct
14 Correct 61 ms 4868 KB Output is correct
15 Correct 632 ms 26196 KB Output is correct
16 Execution timed out 20051 ms 26204 KB Time limit exceeded
17 Halted 0 ms 0 KB -