Submission #1081641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081641		vjudge1	Measures (CEOI22_measures)	C++14	100 / 100	343 ms	48468 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p, r = (1LL << 50);
vector<ll> df, sg, mn, mx, lz, wl, wr;
void push(int i)
{
    mn[i] += lz[i];
    mx[i] += lz[i];
    sg[i] += lz[i];
    if (i < p)
    {
        lz[2 * i] += lz[i];
        lz[2 * i + 1] += lz[i];
    }
    lz[i] = 0;
}
void upd(ll l, ll r, ll i, ll x)
{
    if (wl[i] >= r || wr[i] <= l)
    {
        push(i);
        return;
    }
    if (wl[i] >= l && wr[i] <= r)
    {
        lz[i] += x;
        push(i);
        return;
    }
    push(i);
    upd(l, r, 2 * i, x);
    upd(l, r, 2 * i + 1, x);
    mn[i] = min(mn[2 * i], mn[2 * i + 1]);
    mx[i] = max(mx[2 * i], mx[2 * i + 1]);
    df[i] = max(mx[2 * i + 1] - mn[2 * i], max(df[2 * i], df[2 * i + 1]));
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n, m, d, i, j, z, la;
    cin >> n >> m >> d;
    if (n)
    {
        multiset<ll> s;
        while (n--)
        {
            cin >> i;
            s.insert(i);
        }
        while (m--)
        {
            cin >> i;
            s.insert(i);
            z = 0;
            la = -d;
            for (auto h : s)
            {
                la = max(la + d, h);
                z = max(z, la - h);
            }
            if (z % 2)
                cout << z / 2 << ".5 ";
            else
                cout << z / 2 << " ";
        }
    }
    else
    {
        vector<vector<ll> > q(m, {0, 0});
        vector<ll> in(m), va(m);
        for (i = 0; i < m; i++)
        {
            cin >> q[i][0];
            q[i][1] = i;
        }
        sort(q.begin(), q.end());
        for (i = 0; i < m; i++)
        {
            in[q[i][1]] = i;
            va[q[i][1]] = q[i][0];
        }
        p = m;
        while (p != (p & -p))
            p++;
        wl.resize(2 * p);
        wr.resize(2 * p);
        sg.resize(2 * p);
        df.resize(2 * p);
        lz.resize(2 * p);
        mn.resize(2 * p);
        mx.resize(2 * p);
        for (i = p; i < 2 * p; i++)
        {
            wl[i] = i;
            wr[i] = i + 1;
            mn[i] = r;
            mx[i] = -r;
            sg[i] = 0;
            df[i] = 0;
            lz[i] = 0;
        }
        for (i = p - 1; i > 0; i--)
        {
            wl[i] = wl[2 * i];
            wr[i] = wr[2 * i + 1];
            mn[i] = r;
            mx[i] = -r;
            sg[i] = 0;
            df[i] = 0;
            lz[i] = 0;
        }
        for (i = 0; i < m; i++)
        {
            j = in[i] + p;
            sg[j] -= va[i];
            mn[j] = mx[j] = sg[j];
            upd(j, j + 1, 1, 0);
            upd(j, 2 * p, 1, d);
            z = df[1];
            if (z % 2)
                cout << z / 2 << ".5 ";
            else
                cout << z / 2 << " ";
        }
    }
    return 0;
}

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