oj.uz

Submission #672502

# Submission time Handle Problem Language Result Execution time Memory
672502 2022-12-16T10:54:14 Z FedShat Measures (CEOI22_measures) C++17
45 / 100
 416 ms 32520 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct SegTree {
    struct Node {
        int sum = 0;
        ll mx = -INFLL, mn = INFLL;
        ll push = 0;// +=
    };

    vector<Node> tree;
    int n;

    SegTree(int n) : n(n) {
        tree.resize(4 * n);
    }

    void push(int v, int l, int r) {
        if (l + 1 < r) {
            tree[2 * v + 1].push += tree[v].push;
            tree[2 * v + 2].push += tree[v].push;
        }
        tree[v].mx += tree[v].push;
        tree[v].mn += tree[v].push;
        tree[v].push = 0;
    }

    Node pull(const Node &vl, const Node &vr) {
        Node ans;
        ans.sum = vl.sum + vr.sum;
        ans.mx = max(vl.mx, vr.mx);
        ans.mn = min(vl.mn, vr.mn);
        return ans;
    }

    void update_seg(int v, int l, int r, int li, int ri, ll x) {// +=
        push(v, l, r);
        if (li >= r || l >= ri) {
            return;
        }
        if (li <= l && r <= ri) {
            tree[v].push = x;
            push(v, l, r);
            return;
        }
        int m = (l + r) / 2;
        update_seg(2 * v + 1, l, m, li, ri, x);
        update_seg(2 * v + 2, m, r, li, ri, x);
        tree[v] = pull(tree[2 * v + 1], tree[2 * v + 2]);
    }

    void update_seg(int li, int ri, ll x) {
        update_seg(0, 0, n, li, ri, x);
    }

    void update_point(int v, int l, int r, int i, ll x) {
        push(v, l, r);
        if (l + 1 == r) {
            tree[v].sum = 1;
            tree[v].mx = tree[v].mn = x;
            return;
        }
        int m = (l + r) / 2;
        {
            push(2 * v + 1, l, m);
            push(2 * v + 2, m, r);
        }
        if (i < m) {
            update_point(2 * v + 1, l, m, i, x);
        } else {
            update_point(2 * v + 2, m, r, i, x);
        }
        tree[v] = pull(tree[2 * v + 1], tree[2 * v + 2]);
    }

    void update_point(int i, ll x) {
        update_point(0, 0, n, i, x);
    }

    ll get_mn(int v, int l, int r, int li, int ri) {
        push(v, l, r);
        if (li >= r || l >= ri) {
            return INFLL;
        }
        if (li <= l && r <= ri) {
            return tree[v].mn;
        }
        int m = (l + r) / 2;
        return min(get_mn(2 * v + 1, l, m, li, ri), get_mn(2 * v + 2, m, r, li, ri));
    }

    ll get_mn(int li, int ri) {
        return get_mn(0, 0, n, li, ri);
    }

    ll get_mx(int v, int l, int r, int li, int ri) {
        push(v, l, r);
        if (li >= r || l >= ri) {
            return -INFLL;
        }
        if (li <= l && r <= ri) {
            return tree[v].mx;
        }
        int m = (l + r) / 2;
        return max(get_mx(2 * v + 1, l, m, li, ri), get_mx(2 * v + 2, m, r, li, ri));
    }

    ll get_mx(int li, int ri) {
        return get_mx(0, 0, n, li, ri);
    }

    int get_sum(int v, int l, int r, int li, int ri) {
        push(v, l, r);
        if (li >= r || l >= ri) {
            return 0;
        }
        if (li <= l && r <= ri) {
            return tree[v].sum;
        }
        int m = (l + r) / 2;
        return get_sum(2 * v + 1, l, m, li, ri) + get_sum(2 * v + 2, m, r, li, ri);
    }

    int get_sum(int li, int ri) {
        return get_sum(0, 0, n, li, ri);
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n, m, d;
    cin >> n >> m >> d;
    vector<int> a(n + m);
    cin >> a;
    vector<pair<int, int>> coords;
    for (int i = 0; i < n + m; ++i) {
        coords.push_back({a[i], i});
    }
    sort(coords.begin(), coords.end());
    SegTree st(coords.size());
    ll ans = 0;
    auto add = [&](int i) {
        int it = lower_bound(coords.begin(), coords.end(), pair(a[i], i)) - coords.begin();
        st.update_seg(it + 1, st.n, d);
        int ii = st.get_sum(0, it);
        st.update_point(it, ii * 1ll * d - a[i]);
        ll mn = st.get_mn(0, it);
        ll mx = st.get_mx(it, st.n);
        ans = max(ans, mx - mn);
    };
    for (int i = 0; i < n; ++i) {
        add(i);
    }
    for (int i = n; i < n + m; ++i) {
        add(i);
        if (ans % 2 == 0) {
            cout << ans / 2 << " ";
        } else {
            cout << ans / 2 << ".5 ";
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 404 ms 29504 KB Output is correct
10 Correct 396 ms 29588 KB Output is correct
11 Correct 290 ms 29388 KB Output is correct
12 Correct 317 ms 29248 KB Output is correct
13 Correct 285 ms 28904 KB Output is correct
14 Incorrect 294 ms 29312 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 30432 KB Output is correct
2 Correct 306 ms 32476 KB Output is correct
3 Correct 316 ms 32520 KB Output is correct
4 Correct 297 ms 30000 KB Output is correct
5 Correct 312 ms 31676 KB Output is correct
6 Correct 298 ms 30556 KB Output is correct
7 Correct 304 ms 31740 KB Output is correct
8 Correct 297 ms 30636 KB Output is correct
9 Correct 303 ms 29996 KB Output is correct
10 Correct 316 ms 32496 KB Output is correct
11 Correct 303 ms 30832 KB Output is correct
12 Correct 316 ms 32000 KB Output is correct
13 Correct 302 ms 30124 KB Output is correct
14 Correct 309 ms 32092 KB Output is correct
15 Correct 305 ms 31868 KB Output is correct
16 Correct 306 ms 30028 KB Output is correct
17 Correct 304 ms 31440 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 30432 KB Output is correct
2 Correct 306 ms 32476 KB Output is correct
3 Correct 316 ms 32520 KB Output is correct
4 Correct 297 ms 30000 KB Output is correct
5 Correct 312 ms 31676 KB Output is correct
6 Correct 298 ms 30556 KB Output is correct
7 Correct 304 ms 31740 KB Output is correct
8 Correct 297 ms 30636 KB Output is correct
9 Correct 303 ms 29996 KB Output is correct
10 Correct 316 ms 32496 KB Output is correct
11 Correct 303 ms 30832 KB Output is correct
12 Correct 316 ms 32000 KB Output is correct
13 Correct 302 ms 30124 KB Output is correct
14 Correct 309 ms 32092 KB Output is correct
15 Correct 305 ms 31868 KB Output is correct
16 Correct 306 ms 30028 KB Output is correct
17 Correct 304 ms 31440 KB Output is correct
18 Incorrect 416 ms 30940 KB Output isn't correct
19 Halted 0 ms 0 KB -