oj.uz

Submission #727038

# Submission time Handle Problem Language Result Execution time Memory
727038 2023-04-19T21:33:30 Z rnl42 Measures (CEOI22_measures) C++14
10 / 100
 1500 ms 23876 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; });

    vector<int> arr(N, -INF);

    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);*/
        arr[op.tpos] += op.x + INF;
        for (int i = op.tpos; i < N; i++) {
            arr[i] -= D;
        }
        int maxi = -INF;
        for (int i = 0; i <= op.tpos; i++) {
            maxi = max(maxi, arr[i]);
        }
        int mini = +INF;
        for (int i = op.tpos; i < N; i++) {
            if (arr[i] > -INF) mini = min(mini, arr[i]);
        }
        //cerr << mini << " " << maxi << endl;
        ans = max(ans, maxi-mini);

        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 8 ms 468 KB Output is correct
2 Correct 6 ms 468 KB Output is correct
3 Correct 6 ms 528 KB Output is correct
4 Correct 6 ms 464 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 9 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 468 KB Output is correct
2 Correct 6 ms 468 KB Output is correct
3 Correct 6 ms 528 KB Output is correct
4 Correct 6 ms 464 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 9 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Execution timed out 1552 ms 23876 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1568 ms 22168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1568 ms 22168 KB Time limit exceeded
2 Halted 0 ms 0 KB -