oj.uz

Submission #786823

# Submission time Handle Problem Language Result Execution time Memory
786823 2023-07-18T13:14:38 Z drdilyor Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 16936 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
#include "wombats.h"
using namespace std;
using ll = long long;
const int inf = 1e9 + 1000;

struct SegmentTree {
    using T = int;
    using S = int;
    const T id = inf;
    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<int> 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;
        }
    }

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

    int 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<int> dp(c, inf);
    dp[v2] = 0;
    SegmentTree st(c);
    for (int i = r-1; i >= 0; i--) {

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

        vector<int> ndp(dp);

        for (int j = 0; j < c; j++) {
            int 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--) {
            int 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 139 ms 4856 KB Output is correct
2 Correct 137 ms 4844 KB Output is correct
3 Correct 196 ms 6392 KB Output is correct
4 Correct 140 ms 4848 KB Output is correct
5 Correct 141 ms 4840 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 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 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 60 ms 1320 KB Output is correct
12 Correct 2 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 624 KB Output is correct
2 Correct 217 ms 620 KB Output is correct
3 Correct 222 ms 620 KB Output is correct
4 Correct 207 ms 716 KB Output is correct
5 Correct 210 ms 620 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 105 ms 620 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 8760 KB Output is correct
2 Correct 597 ms 8780 KB Output is correct
3 Correct 598 ms 8880 KB Output is correct
4 Correct 626 ms 9460 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 640 KB Output is correct
2 Correct 207 ms 620 KB Output is correct
3 Correct 205 ms 596 KB Output is correct
4 Correct 207 ms 636 KB Output is correct
5 Correct 213 ms 620 KB Output is correct
6 Correct 603 ms 8768 KB Output is correct
7 Correct 601 ms 8784 KB Output is correct
8 Correct 646 ms 8756 KB Output is correct
9 Correct 621 ms 9536 KB Output is correct
10 Correct 136 ms 4840 KB Output is correct
11 Correct 142 ms 4820 KB Output is correct
12 Correct 194 ms 6404 KB Output is correct
13 Correct 141 ms 4820 KB Output is correct
14 Correct 140 ms 4840 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 59 ms 1280 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 106 ms 596 KB Output is correct
28 Execution timed out 20009 ms 12592 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 596 KB Output is correct
2 Correct 209 ms 624 KB Output is correct
3 Correct 208 ms 624 KB Output is correct
4 Correct 207 ms 620 KB Output is correct
5 Correct 213 ms 620 KB Output is correct
6 Correct 598 ms 8776 KB Output is correct
7 Correct 603 ms 8756 KB Output is correct
8 Correct 594 ms 8760 KB Output is correct
9 Correct 621 ms 9436 KB Output is correct
10 Correct 140 ms 4820 KB Output is correct
11 Correct 139 ms 4820 KB Output is correct
12 Correct 198 ms 6380 KB Output is correct
13 Correct 150 ms 4820 KB Output is correct
14 Correct 139 ms 4844 KB Output is correct
15 Correct 1639 ms 16752 KB Output is correct
16 Execution timed out 20035 ms 16936 KB Time limit exceeded
17 Halted 0 ms 0 KB -