oj.uz

Submission #672506

# Submission time Handle Problem Language Result Execution time Memory
672506 2022-12-16T11:03:31 Z FedShat Measures (CEOI22_measures) C++17
100 / 100
 476 ms 32580 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 + 1);
        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 3 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 2 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
14.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 3 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 2 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 476 ms 27860 KB Output is correct
10 Correct 405 ms 27844 KB Output is correct
11 Correct 298 ms 27844 KB Output is correct
12 Correct 322 ms 27772 KB Output is correct
13 Correct 288 ms 27856 KB Output is correct
14 Correct 299 ms 27860 KB Output is correct
15 Correct 404 ms 28920 KB Output is correct
16 Correct 297 ms 29208 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 28820 KB Output is correct
2 Correct 325 ms 30748 KB Output is correct
3 Correct 317 ms 30656 KB Output is correct
4 Correct 320 ms 28652 KB Output is correct
5 Correct 338 ms 29880 KB Output is correct
6 Correct 315 ms 29004 KB Output is correct
7 Correct 307 ms 29956 KB Output is correct
8 Correct 316 ms 28700 KB Output is correct
9 Correct 303 ms 28712 KB Output is correct
10 Correct 308 ms 30968 KB Output is correct
11 Correct 321 ms 29444 KB Output is correct
12 Correct 327 ms 30404 KB Output is correct
13 Correct 300 ms 28644 KB Output is correct
14 Correct 323 ms 30496 KB Output is correct
15 Correct 311 ms 30356 KB Output is correct
16 Correct 331 ms 28556 KB Output is correct
17 Correct 308 ms 29932 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 28820 KB Output is correct
2 Correct 325 ms 30748 KB Output is correct
3 Correct 317 ms 30656 KB Output is correct
4 Correct 320 ms 28652 KB Output is correct
5 Correct 338 ms 29880 KB Output is correct
6 Correct 315 ms 29004 KB Output is correct
7 Correct 307 ms 29956 KB Output is correct
8 Correct 316 ms 28700 KB Output is correct
9 Correct 303 ms 28712 KB Output is correct
10 Correct 308 ms 30968 KB Output is correct
11 Correct 321 ms 29444 KB Output is correct
12 Correct 327 ms 30404 KB Output is correct
13 Correct 300 ms 28644 KB Output is correct
14 Correct 323 ms 30496 KB Output is correct
15 Correct 311 ms 30356 KB Output is correct
16 Correct 331 ms 28556 KB Output is correct
17 Correct 308 ms 29932 KB Output is correct
18 Correct 442 ms 29028 KB Output is correct
19 Correct 433 ms 32308 KB Output is correct
20 Correct 329 ms 32580 KB Output is correct
21 Correct 342 ms 30340 KB Output is correct
22 Correct 373 ms 30784 KB Output is correct
23 Correct 342 ms 30636 KB Output is correct
24 Correct 417 ms 30932 KB Output is correct
25 Correct 315 ms 30388 KB Output is correct
26 Correct 457 ms 30104 KB Output is correct
27 Correct 434 ms 32216 KB Output is correct
28 Correct 369 ms 30904 KB Output is correct
29 Correct 427 ms 30920 KB Output is correct
30 Correct 345 ms 29800 KB Output is correct
31 Correct 339 ms 32204 KB Output is correct
32 Correct 367 ms 31172 KB Output is correct
33 Correct 429 ms 28860 KB Output is correct
34 Correct 371 ms 31068 KB Output is correct