Submission #1228476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228476		spetr	Measures (CEOI22_measures)	C++20	0 / 100	465 ms	74228 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf = 1e18;
using vl = vector<ll>;
using vll = vector<vl>;

vll tree;

void push(ll i) {
    if (2*i+2 < (ll)tree.size()) {
        ll lazy = tree[i][5];
        for (int ch : {1,2}) {
            ll cidx = 2*i + ch;
            tree[cidx][3] += lazy;
            tree[cidx][4] += lazy;
            tree[cidx][5] += lazy;
        }
        tree[i][5] = 0;
    }
}

ll secti(ll l, ll r, ll L, ll R, ll i) {
    if (l > r) return 0;                // ošetření prázdného intervalu
    push(i);
    if (r < L || l > R) return 0;
    if (l <= L && R <= r) return tree[i][2];
    ll mid = (L+R)/2;
    return secti(l, r, L, mid, 2*i+1)
         + secti(l, r, mid+1, R, 2*i+2);
}

void update(ll idx, ll c) {
    vector<ll> st;
    ll i = idx;
    while (i) {
        st.push_back(i);
        i = (i-1)/2;
    }
    st.push_back(0);
    for (int j = (int)st.size()-1; j >= 0; --j) {
        ll p = st[j];
        push(p);
        tree[p][2]++;
        tree[p][3] = min(tree[p][3], c);
        tree[p][4] = max(tree[p][4], c);
    }
}

void pricti(ll l, ll r, ll L, ll R, ll c, ll i) {
    push(i);
    if (r < L || l > R) return;
    if (l <= L && R <= r) {
        tree[i][3] += c;
        tree[i][4] += c;
        tree[i][5] += c;
        return;
    }
    ll mid = (L+R)/2;
    pricti(l, r, L, mid, c, 2*i+1);
    pricti(l, r, mid+1, R, c, 2*i+2);
}

ll najdi_minimum(ll l, ll r, ll L, ll R, ll i) {
    push(i);
    if (r < L || l > R) return inf;
    if (l <= L && R <= r) return tree[i][3];
    ll mid = (L+R)/2;
    return min(najdi_minimum(l, r, L, mid, 2*i+1),
               najdi_minimum(l, r, mid+1, R, 2*i+2));
}

ll najdi_maximum(ll l, ll r, ll L, ll R, ll i) {
    push(i);
    if (r < L || l > R) return -inf;
    if (l <= L && R <= r) return tree[i][4];
    ll mid = (L+R)/2;
    return max(najdi_maximum(l, r, L, mid, 2*i+1),
               najdi_maximum(l, r, mid+1, R, 2*i+2));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m, d;
    cin >> n >> m >> d;
    vl nums(n+m);
    for (ll i = 0; i < n+m; i++) cin >> nums[i];

    // komprese souřadnic
    set<ll> s(nums.begin(), nums.end());
    map<ll,ll> mp;
    ll k = 0;
    for (ll x : s) mp[x] = k++;

    vl cnt(k), idx(k);
    for (ll x : nums) cnt[mp[x]]++;
    for (int i = 1; i < k; i++) idx[i] = idx[i-1] + cnt[i-1];

    vl sorted = nums;
    sort(sorted.begin(), sorted.end());

    ll size_leaves = 1;
    while (size_leaves < n+m) size_leaves <<= 1;

    // správné budování stromu
    tree.assign(2*size_leaves - 1, {inf,inf,0,inf,-inf,0});
    for (ll i = 0; i < n+m; i++)
        tree[size_leaves-1 + i] = {sorted[i], sorted[i], 0, inf, -inf, 0};
    for (ll i = size_leaves-2; i >= 0; --i) {
        tree[i][0] = tree[2*i+1][0];
        tree[i][1] = tree[2*i+2][1];
    }

    for (ll i = 0; i < n+m; i++) {
        ll pos = idx[mp[nums[i]]]++;
        ll cnt_less = secti(0, pos-1, 0, size_leaves-1, 0);
        update(size_leaves-1 + pos, nums[i] - cnt_less*d);
        pricti(pos+1, size_leaves-1, 0, size_leaves-1, -d, 0);
        ll mn = najdi_minimum(pos, size_leaves-1, 0, size_leaves-1, 0);
        ll mx = najdi_maximum(0, pos, 0, size_leaves-1, 0);
        if (i >= n) {
            double delta = mx - mn;
            cout << (delta * 0.5) << " ";
        }
    }

    return 0;
}

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