Submission #657200

#	Time	Username	Problem	Language	Result	Execution time	Memory
657200		dooompy	Measures (CEOI22_measures)	C++17	86 / 100	190 ms	41872 KiB

Main

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

ll pos[200005];
ll val[200005];

struct node {
    ll mn, mx, lz, ans;
};

node tree[200005 * 4];

void sett(int x, int l, int r, int p, int v) {
    if (l == r) {
        tree[x].mn = tree[x].mx = v + tree[x].lz;
        tree[x].ans = 0;
        return;
    }

    int mid = (l + r) / 2;

    if (p <= mid) sett(2 * x, l, mid, p, v);
    else sett(2 * x + 1, mid + 1, r, p, v);

    tree[x].mn = tree[x].lz + min(tree[2 * x].mn, tree[2 * x + 1].mn);
    tree[x].mx = tree[x].lz + max(tree[2 * x].mx, tree[2 * x + 1].mx);
    tree[x].ans = max({tree[2 * x].ans, tree[2 * x + 1].ans, tree[2 * x].mx - tree[2 * x + 1].mn});
}

void add(int x, int l, int r, int ql, int qr, int v) {
    if (ql <= l && r <= qr) {
        tree[x].lz += v;
        tree[x].mx += v;
        tree[x].mn += v;
        return;
    }

    if (l > qr || ql > r) return;

    int mid = (l + r) / 2;

    add(2 * x, l, mid, ql, qr, v);
    add(2 * x + 1, mid + 1, r, ql, qr, v);

    tree[x].mn = tree[x].lz + min(tree[2 * x].mn, tree[2 * x + 1].mn);
    tree[x].mx = tree[x].lz + max(tree[2 * x].mx, tree[2 * x + 1].mx);
    tree[x].ans = max({tree[2 * x].ans, tree[2 * x + 1].ans, tree[2 * x].mx - tree[2 * x + 1].mn});
}

void build(int x, int l, int r) {
    tree[x].mn = 1e15;
    tree[x].mx = -1e15;
    tree[x].ans = -1e15;


    if (l == r) {
        return;
    }

    int mid = (l + r) / 2;

    build(2 * x, l, mid);
    build(2 * x + 1, mid + 1, r);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, m, d; cin >> n >> m >> d;

    build(1, 1, 200000);
    vector<pair<ll, ll>> v;
    for (int i = 1; i <= n + m; i++) {
        int t; cin >> t;
        val[i] = t;
        v.push_back({t, i});
    }

    sort(v.begin(), v.end());

    for (int i = 1; i <= n + m; i++) {
        pos[v[i - 1].second] = i;
    }

    for (int i = 1; i <= n; i++) {
        sett(1, 1, 200000, pos[i], val[i]);
        add(1, 1, 200000, pos[i] + 1, 200000, -d);
    }

    for (int i = n + 1; i <= n + m; i++) {
        sett(1, 1, 200000, pos[i], val[i]);
        add(1, 1, 200000, pos[i] + 1, 200000, -d);

        ll res = tree[1].ans;
        
        if (res % 2 == 1) {
            cout << res / 2  <<  ".5 ";
        } else cout << res / 2 << " " ;
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41