Submission #1228459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228459		spetr	Measures (CEOI22_measures)	C++20	0 / 100	677 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()){
        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 = 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];

    // coordinate compression
    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];

    // build sorted array of original values
    vl sorted = nums;
    sort(sorted.begin(), sorted.end());

    // size of segment-tree leaves
    ll size_leaves = 1;
    while (size_leaves < n+m) size_leaves <<= 1;

    // allocate full tree
    tree.assign(2*size_leaves - 1, {inf, inf, 0, inf, -inf, 0});
    // fill leaves
    for (ll i = 0; i < n+m; i++){
        tree[size_leaves - 1 + i] = {sorted[i], sorted[i], 0, inf, -inf, 0};
    }
    // build parents
    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];
        // count, min, max, lazy remain defaults
    }

    // process each person
    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