oj.uz

Submission #862148

# Submission time Handle Problem Language Result Execution time Memory
862148 2023-10-17T14:46:10 Z vgtcross Measures (CEOI22_measures) C++17
35 / 100
 229 ms 42212 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(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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 40076 KB Output is correct
2 Correct 143 ms 42144 KB Output is correct
3 Correct 142 ms 42064 KB Output is correct
4 Correct 129 ms 39764 KB Output is correct
5 Correct 162 ms 41044 KB Output is correct
6 Correct 130 ms 40272 KB Output is correct
7 Correct 133 ms 41296 KB Output is correct
8 Correct 130 ms 39832 KB Output is correct
9 Correct 131 ms 39920 KB Output is correct
10 Correct 136 ms 42212 KB Output is correct
11 Correct 133 ms 40584 KB Output is correct
12 Correct 135 ms 41672 KB Output is correct
13 Correct 132 ms 39720 KB Output is correct
14 Correct 133 ms 41740 KB Output is correct
15 Correct 133 ms 41696 KB Output is correct
16 Correct 129 ms 39504 KB Output is correct
17 Correct 133 ms 41300 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 40076 KB Output is correct
2 Correct 143 ms 42144 KB Output is correct
3 Correct 142 ms 42064 KB Output is correct
4 Correct 129 ms 39764 KB Output is correct
5 Correct 162 ms 41044 KB Output is correct
6 Correct 130 ms 40272 KB Output is correct
7 Correct 133 ms 41296 KB Output is correct
8 Correct 130 ms 39832 KB Output is correct
9 Correct 131 ms 39920 KB Output is correct
10 Correct 136 ms 42212 KB Output is correct
11 Correct 133 ms 40584 KB Output is correct
12 Correct 135 ms 41672 KB Output is correct
13 Correct 132 ms 39720 KB Output is correct
14 Correct 133 ms 41740 KB Output is correct
15 Correct 133 ms 41696 KB Output is correct
16 Correct 129 ms 39504 KB Output is correct
17 Correct 133 ms 41300 KB Output is correct
18 Incorrect 229 ms 41016 KB Output isn't correct
19 Halted 0 ms 0 KB -