oj.uz

Submission #862153

# Submission time Handle Problem Language Result Execution time Memory
862153 2023-10-17T14:49:09 Z vgtcross Measures (CEOI22_measures) C++17
100 / 100
 243 ms 42292 KB 
#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(pos[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(pos[i]+1, n+m-1, d);
        print_ans(seg.maxd);
    }
    cout << '\n';
    seg.del();
}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 728 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 728 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 226 ms 39168 KB Output is correct
10 Correct 219 ms 38996 KB Output is correct
11 Correct 128 ms 39064 KB Output is correct
12 Correct 165 ms 38992 KB Output is correct
13 Correct 122 ms 38480 KB Output is correct
14 Correct 130 ms 39076 KB Output is correct
15 Correct 231 ms 38504 KB Output is correct
16 Correct 128 ms 39252 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 40020 KB Output is correct
2 Correct 144 ms 41812 KB Output is correct
3 Correct 146 ms 42152 KB Output is correct
4 Correct 132 ms 39584 KB Output is correct
5 Correct 136 ms 41036 KB Output is correct
6 Correct 135 ms 40016 KB Output is correct
7 Correct 138 ms 41104 KB Output is correct
8 Correct 151 ms 39760 KB Output is correct
9 Correct 140 ms 39776 KB Output is correct
10 Correct 140 ms 42068 KB Output is correct
11 Correct 137 ms 40592 KB Output is correct
12 Correct 143 ms 41576 KB Output is correct
13 Correct 134 ms 39764 KB Output is correct
14 Correct 141 ms 41556 KB Output is correct
15 Correct 142 ms 41808 KB Output is correct
16 Correct 142 ms 39508 KB Output is correct
17 Correct 136 ms 41044 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 40020 KB Output is correct
2 Correct 144 ms 41812 KB Output is correct
3 Correct 146 ms 42152 KB Output is correct
4 Correct 132 ms 39584 KB Output is correct
5 Correct 136 ms 41036 KB Output is correct
6 Correct 135 ms 40016 KB Output is correct
7 Correct 138 ms 41104 KB Output is correct
8 Correct 151 ms 39760 KB Output is correct
9 Correct 140 ms 39776 KB Output is correct
10 Correct 140 ms 42068 KB Output is correct
11 Correct 137 ms 40592 KB Output is correct
12 Correct 143 ms 41576 KB Output is correct
13 Correct 134 ms 39764 KB Output is correct
14 Correct 141 ms 41556 KB Output is correct
15 Correct 142 ms 41808 KB Output is correct
16 Correct 142 ms 39508 KB Output is correct
17 Correct 136 ms 41044 KB Output is correct
18 Correct 242 ms 40340 KB Output is correct
19 Correct 236 ms 41860 KB Output is correct
20 Correct 146 ms 41932 KB Output is correct
21 Correct 161 ms 40104 KB Output is correct
22 Correct 192 ms 40280 KB Output is correct
23 Correct 141 ms 40076 KB Output is correct
24 Correct 228 ms 40788 KB Output is correct
25 Correct 132 ms 39732 KB Output is correct
26 Correct 235 ms 40100 KB Output is correct
27 Correct 243 ms 42292 KB Output is correct
28 Correct 195 ms 40224 KB Output is correct
29 Correct 215 ms 41616 KB Output is correct
30 Correct 160 ms 39764 KB Output is correct
31 Correct 163 ms 41880 KB Output is correct
32 Correct 143 ms 41552 KB Output is correct
33 Correct 224 ms 39508 KB Output is correct
34 Correct 162 ms 41044 KB Output is correct