oj.uz

Submission #727040

# Submission time Handle Problem Language Result Execution time Memory
727040 2023-04-19T21:46:14 Z rnl42 Measures (CEOI22_measures) C++14
100 / 100
 302 ms 22404 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

constexpr long long INF = 1e15;

struct Operation {
    int x;
    int tpos;
    int id;
};

struct Node {
    int maxval = -INF;
    int minval = +INF;
    int toapply = 0;
};

int N, M, D;
vector<Operation> ops;
int ans = 0;
vector<Node> tree;

inline void pushval(int idx) {
    if (tree[idx].toapply != 0) {
        if ((idx<<1)+1 < (int)tree.size()) {
            tree[(idx<<1)].maxval += tree[idx].toapply;
            tree[(idx<<1)].minval += tree[idx].toapply;
            tree[(idx<<1)].toapply += tree[idx].toapply;
            tree[(idx<<1)+1].maxval += tree[idx].toapply;
            tree[(idx<<1)+1].minval += tree[idx].toapply;
            tree[(idx<<1)+1].toapply += tree[idx].toapply;
        }
        tree[idx].toapply = 0;
    }
}

int queryminmax(int reql, int reqr, int idx, int l, int r, bool _max) {
    if (reqr < l || reql > r) {
        return _max ? -INF : INF;
    } else if (reql <= l && r <= reqr) {
        pushval(idx);
        return _max ? tree[idx].maxval : tree[idx].minval;
    } else {
        pushval(idx);
        auto a = queryminmax(reql, reqr, idx<<1, l, (l+r)>>1, _max);
        auto b = queryminmax(reql, reqr, (idx<<1)+1, ((l+r)>>1)+1, r, _max);
        return _max ? max(a, b) : min(a, b);
    }
}

bool type;
void incrval(int reql, int reqr, int idx, int l, int r, int val) {
    if (reqr < l || reql > r) {
        return;
    } else if (reql <= l && r <= reqr) {
        pushval(idx);
        if (type) {
            tree[idx].maxval += INF;
            tree[idx].minval -= INF;
        }
        tree[idx].maxval += val;
        tree[idx].minval += val;
        tree[idx].toapply = val;
    } else {
        pushval(idx);
        incrval(reql, reqr, idx<<1, l, (l+r)>>1, val);
        incrval(reql, reqr, (idx<<1)+1, ((l+r)>>1)+1, r, val);
        tree[idx].minval = min(tree[idx<<1].minval, tree[(idx<<1)+1].minval);
        tree[idx].maxval = max(tree[idx<<1].maxval, tree[(idx<<1)+1].maxval);
    }
}

signed main() {
    ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
    cin >> N >> M >> D;
    N += M;
    M = N-M;
    ops.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> ops[i].x;
        ops[i].id = i;
    }
    sort(ops.begin(), ops.end(), [](const Operation a, const Operation b) { return a.x < b.x; });
    for (int i = 0; i < N; i++) { ops[i].tpos = i; }
    sort(ops.begin(), ops.end(), [](const Operation a, const Operation b) { return a.id < b.id; });

    tree.resize(2ll<<__lg((N<<1)-1));
    int ans = 0;
    for (int _i_op = 0; _i_op < N; _i_op++) {
        auto& op = ops[_i_op];
        type = true;
        incrval(op.tpos, op.tpos, 1, 0, N-1, op.x);
        type = false;
        incrval(op.tpos, N-1, 1, 0, N-1, -D);

        int truc = queryminmax(0, op.tpos, 1, 0, N-1, true) - queryminmax(op.tpos, N-1, 1, 0, N-1, false);
        ans = max(ans, truc);

        if (_i_op >= M) {
            cout << (ans>>1); if (ans & 1) cout << ".5";
            cout << (_i_op == N-1 ? '\n' : ' ');
        }
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 452 KB Output is correct
5 Correct 2 ms 452 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 452 KB Output is correct
9 Correct 273 ms 17328 KB Output is correct
10 Correct 259 ms 19148 KB Output is correct
11 Correct 199 ms 19284 KB Output is correct
12 Correct 247 ms 19256 KB Output is correct
13 Correct 168 ms 18796 KB Output is correct
14 Correct 202 ms 19332 KB Output is correct
15 Correct 260 ms 18700 KB Output is correct
16 Correct 167 ms 19260 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 18336 KB Output is correct
2 Correct 200 ms 22160 KB Output is correct
3 Correct 196 ms 22196 KB Output is correct
4 Correct 185 ms 19976 KB Output is correct
5 Correct 191 ms 21320 KB Output is correct
6 Correct 184 ms 20404 KB Output is correct
7 Correct 190 ms 21372 KB Output is correct
8 Correct 189 ms 20044 KB Output is correct
9 Correct 190 ms 19932 KB Output is correct
10 Correct 196 ms 22348 KB Output is correct
11 Correct 195 ms 20740 KB Output is correct
12 Correct 195 ms 21708 KB Output is correct
13 Correct 186 ms 19984 KB Output is correct
14 Correct 190 ms 21964 KB Output is correct
15 Correct 195 ms 21812 KB Output is correct
16 Correct 187 ms 19520 KB Output is correct
17 Correct 190 ms 21248 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 18336 KB Output is correct
2 Correct 200 ms 22160 KB Output is correct
3 Correct 196 ms 22196 KB Output is correct
4 Correct 185 ms 19976 KB Output is correct
5 Correct 191 ms 21320 KB Output is correct
6 Correct 184 ms 20404 KB Output is correct
7 Correct 190 ms 21372 KB Output is correct
8 Correct 189 ms 20044 KB Output is correct
9 Correct 190 ms 19932 KB Output is correct
10 Correct 196 ms 22348 KB Output is correct
11 Correct 195 ms 20740 KB Output is correct
12 Correct 195 ms 21708 KB Output is correct
13 Correct 186 ms 19984 KB Output is correct
14 Correct 190 ms 21964 KB Output is correct
15 Correct 195 ms 21812 KB Output is correct
16 Correct 187 ms 19520 KB Output is correct
17 Correct 190 ms 21248 KB Output is correct
18 Correct 302 ms 20428 KB Output is correct
19 Correct 300 ms 22116 KB Output is correct
20 Correct 198 ms 22144 KB Output is correct
21 Correct 235 ms 20132 KB Output is correct
22 Correct 244 ms 20496 KB Output is correct
23 Correct 221 ms 20484 KB Output is correct
24 Correct 289 ms 20880 KB Output is correct
25 Correct 188 ms 19928 KB Output is correct
26 Correct 289 ms 19996 KB Output is correct
27 Correct 290 ms 22404 KB Output is correct
28 Correct 241 ms 20444 KB Output is correct
29 Correct 268 ms 21772 KB Output is correct
30 Correct 248 ms 19860 KB Output is correct
31 Correct 245 ms 21956 KB Output is correct
32 Correct 225 ms 21768 KB Output is correct
33 Correct 292 ms 19592 KB Output is correct
34 Correct 245 ms 21296 KB Output is correct