제출 #1228460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228460		spetr	Measures (CEOI22_measures)	C++20	0 / 100	423 ms	74296 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()){
        tree[2*i+1][3] += tree[i][5];
        tree[2*i+1][4] += tree[i][5];
        tree[2*i+1][5] += tree[i][5];
        tree[2*i+2][3] += tree[i][5];
        tree[2*i+2][4] += tree[i][5];
        tree[2*i+2][5] += tree[i][5];
        tree[i][5] = 0;
    }
}

ll secti(ll l, ll r, ll L, ll R, ll i){
    if (l > r) return 0;
    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> positions;
    ll i = idx;
    while (i != 0){
        positions.push_back(i);
        i = (i-1)/2;
    }
    positions.push_back(0);
    for (int j = (int)positions.size()-1; j >= 0; --j){
        ll p = positions[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 idx = 0;
    for (ll x : s) 
        mp[x] = idx++;

    vl count(s.size(), 0), index(s.size(), 0);
    for (ll x : nums) 
        count[mp[x]]++;
    for (size_t i = 1; i < count.size(); i++)
        index[i] = index[i-1] + count[i-1];

    // seřazené hodnoty
    vl sorted = nums;
    sort(sorted.begin(), sorted.end());

    // velkost listů
    ll size_leaves = 1;
    while (size_leaves < n+m) size_leaves <<= 1;

    // alokace stromu
    tree.assign(2*size_leaves - 1, {inf, inf, 0, inf, -inf, 0});
    // naplnění listů
    for (ll i = 0; i < n+m; i++){
        tree[size_leaves-1 + i] = {sorted[i], sorted[i], 0, inf, -inf, 0};
    }
    // sestavení rodičů
    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];
    }

    // zpracování přidávání lidí
    for (ll i = 0; i < n+m; i++){
        ll pos = index[mp[nums[i]]]++;
        ll cnt = secti(0, pos-1, 0, size_leaves-1, 0);
        update(size_leaves-1 + pos, nums[i] - cnt*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