oj.uz

Submission #786872

# Submission time Handle Problem Language Result Execution time Memory
786872 2023-07-18T14:05:23 Z drdilyor Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 16976 KB 
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

#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;
int level[5000][200];
int pass[5000][200];
int dist[200][200];

vector<char> 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) {
            if (r < 0) return 0;
            return level[i][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;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c-1; j++) {
            level[i][j] = h[i][j];
            if (j) level[i][j] += level[i][j-1];
        }
    }

    for (int i = 0; i < r-1; i++) {
        for (int j = 0; j < c; j++) {
            pass[i][j] =v[i][j];
        }
    }
    dirty.assign(c, 1);
    memset(dist, 0, sizeof(dist));
}

void changeH(int32_t p, int32_t q, int32_t w) {
    int actual = level[p][q];
    if (q) actual -= level[p][q-1];
    int diff = w - actual;
    for (int i = q; i < c-1; i++)
        level[p][i] += diff;
    dirty.assign(c, 1);
}

void changeV(int32_t p, int32_t q, int32_t w) {
    pass[p][q] = w;
    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 113 ms 8276 KB Output is correct
2 Correct 116 ms 8276 KB Output is correct
3 Correct 173 ms 9844 KB Output is correct
4 Correct 115 ms 8284 KB Output is correct
5 Correct 116 ms 8276 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 0 ms 468 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 57 ms 1500 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 776 KB Output is correct
2 Correct 182 ms 852 KB Output is correct
3 Correct 176 ms 856 KB Output is correct
4 Correct 176 ms 852 KB Output is correct
5 Correct 179 ms 852 KB Output is correct
6 Correct 1 ms 448 KB Output is correct
7 Correct 1 ms 448 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 89 ms 856 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 16096 KB Output is correct
2 Correct 461 ms 16152 KB Output is correct
3 Correct 448 ms 16168 KB Output is correct
4 Correct 482 ms 16944 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 780 KB Output is correct
2 Correct 192 ms 852 KB Output is correct
3 Correct 176 ms 852 KB Output is correct
4 Correct 176 ms 852 KB Output is correct
5 Correct 179 ms 868 KB Output is correct
6 Correct 451 ms 16084 KB Output is correct
7 Correct 450 ms 16284 KB Output is correct
8 Correct 460 ms 16172 KB Output is correct
9 Correct 483 ms 16948 KB Output is correct
10 Correct 118 ms 8268 KB Output is correct
11 Correct 116 ms 8308 KB Output is correct
12 Correct 173 ms 9956 KB Output is correct
13 Correct 117 ms 8276 KB Output is correct
14 Correct 120 ms 8308 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 452 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 2 ms 452 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 62 ms 1604 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 101 ms 852 KB Output is correct
28 Execution timed out 20071 ms 16224 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 780 KB Output is correct
2 Correct 186 ms 848 KB Output is correct
3 Correct 176 ms 856 KB Output is correct
4 Correct 185 ms 864 KB Output is correct
5 Correct 177 ms 872 KB Output is correct
6 Correct 449 ms 16176 KB Output is correct
7 Correct 451 ms 16164 KB Output is correct
8 Correct 450 ms 16172 KB Output is correct
9 Correct 484 ms 16976 KB Output is correct
10 Correct 119 ms 8300 KB Output is correct
11 Correct 118 ms 8312 KB Output is correct
12 Correct 179 ms 10072 KB Output is correct
13 Correct 117 ms 8312 KB Output is correct
14 Correct 120 ms 8308 KB Output is correct
15 Correct 1386 ms 16352 KB Output is correct
16 Execution timed out 20094 ms 16476 KB Time limit exceeded
17 Halted 0 ms 0 KB -