Submission #672506

#	Time	Username	Problem	Language	Result	Execution time	Memory
672506		FedShat	Measures (CEOI22_measures)	C++17	100 / 100	476 ms	32580 KiB

Main

#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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41