oj.uz

Submission #727035

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

constexpr long long INF = 1e18;

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

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);
    }
}

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 (tree[idx].maxval < tree[idx].minval && reql == reqr) {
            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];
        incrval(op.tpos, op.tpos, 1, 0, N-1, op.x);
        incrval(op.tpos, N-1, 1, 0, N-1, -D);

        int truc = queryminmax(0, op.prevtpos, 1, 0, N-1, true) - queryminmax(op.prevtpos, 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
0 / 10.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 41.0

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