Submission #862148

#	Time	Username	Problem	Language	Result	Execution time	Memory
862148		vgtcross	Measures (CEOI22_measures)	C++17	35 / 100	229 ms	42212 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

struct segtree {
    ll minv, maxv, maxd;
    ll cnt;
    int l, r, m;
    ll lazy;
    segtree *lc = nullptr, *rc = nullptr;
    
    segtree(int L, int R) {
        l = L;
        r = R;
        m = (l + r) / 2;
        minv = 1e18;
        maxv = -1e18;
        maxd = -1e18;
        cnt = 0;
        lazy = 0;
        if (l == r) return;
        lc = new segtree(l, m);
        rc = new segtree(m+1, r);
    }
    
    void push() {
        lc->lazy += lazy;
        lc->minv += lazy;
        lc->maxv += lazy;
        rc->lazy += lazy;
        rc->minv += lazy;
        rc->maxv += lazy;
        lazy = 0;
    }
    
    void point_set(int i, ll v) {
        if (l == i && i == r) {
            minv = maxv = v;
            maxd = 0;
            cnt = 1;
            return;
        }
        
        push();
        if (i <= m) lc->point_set(i, v);
        else rc->point_set(i, v);
        minv = min(lc->minv, rc->minv);
        maxv = max(lc->maxv, rc->maxv);
        maxd = max(rc->maxv - lc->minv, max(lc->maxd, rc->maxd));
        cnt = lc->cnt + rc->cnt;
    }
    
    void range_add(int L, int R, int v) {
        if (L > R) return;
        if (l == L && r == R) {
            lazy += v;
            minv += v;
            maxv += v;
            return;
        }
        push();
        lc->range_add(L, min(R, m), v);
        rc->range_add(max(m+1, L), R, v);
        minv = min(lc->minv, rc->minv);
        maxv = max(lc->maxv, rc->maxv);
        maxd = max(rc->maxv - lc->minv, max(lc->maxd, rc->maxd));
        cnt = lc->cnt + rc->cnt;
    }
    
    int get_idx(int i) {
        if (l == i && i == r) return 0;
        push();
        if (i <= m) return lc->get_idx(i);
        else return lc->cnt + rc->get_idx(i);
    }
    
    void del() {
        if (lc != nullptr) lc->del();
        if (rc != nullptr) rc->del();
        delete lc;
        delete rc;
    }
};

void print_ans(ll ans) {
    cout << ans/2;
    if (ans & 1) cout << ".5";
    cout << ' ';
}

void solve() {
    ll n, m, d;
    cin >> n >> m >> d;
    
    vector<ll> v(n + m);
    vector<pll> v2(n + m);
    for (int i = 0; i < n+m; ++i) {
        cin >> v[i];
        v2[i] = {v[i], i};
    }
    
    sort(v2.begin(), v2.end());
    vector<int> pos(n+m);
    for (int i = 0; i < n+m; ++i) pos[v2[i].second] = i;
    
    segtree seg(0, n+m-1);
    for (int i = 0; i < n; ++i) {
        int j = seg.get_idx(pos[i]);
        seg.point_set(pos[i], d*j - v[i]);
        seg.range_add(i+1, n+m-1, d);
    }
    for (int i = n; i < n+m; ++i) {
        int j = seg.get_idx(pos[i]);
        seg.point_set(pos[i], d*j - v[i]);
        seg.range_add(i+1, n+m-1, d);
        print_ans(seg.maxd);
    }
    cout << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    solve();
}

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