oj.uz

Submission #723327

# Submission time Handle Problem Language Result Execution time Memory
723327 2023-04-13T15:38:20 Z someone Measures (CEOI22_measures) C++14
0 / 100
 1500 ms 2076 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int M = 1 << 18, N = 2 * M, INF = 1e18 + 42;

struct Node {
    int mini, maxi, lazy, nb;
} node[N];

pair<int, int> pii[N];
int n, m, d, a[N], id[N];
/*
void applyOp(int i, int add) {
    node[i].mini += add;
    node[i].maxi += add;
    node[i].lazy += add;
}

void upd(int i) {
    node[i].mini = INF;
    node[i].maxi = -INF;
    if(node[i*2].nb) {
        node[i].mini = min(node[i].mini, node[i*2].mini);
        node[i].maxi = max(node[i].maxi, node[i*2].maxi);
    }
    if(node[i*2+1].nb) {
        node[i].mini = min(node[i].mini, node[i*2+1].mini);
        node[i].maxi = max(node[i].maxi, node[i*2+1].maxi);
    }
}

void propage(int i) {
    applyOp(i*2, node[i].lazy);
    applyOp(i*2+1, node[i].lazy);
    node[i].lazy = 0;
}

void addNew(int i, int deb, int fin, int p, int val) {
    if(fin <= p || p < deb) return;
    if(fin - deb == 1 && deb == p) {
        node[i].nb = 1;
        node[i].lazy = 0;
        node[i].mini += val;
        node[i].maxi += val;
        return;
    }
    propage(i);
    int mid = ((deb + fin) >> 1);
    addNew(i*2, deb, mid, p, val);
    addNew(i*2+1, mid, fin, p, val);
    node[i].nb = node[i*2].nb + node[i*2+1].nb;
    upd(i);
}

void update(int i, int deb, int fin, int l, int r, int add) {
    if(fin <= l || r <= deb) return;
    if(l <= deb && fin <= r) {
        applyOp(i, add);
        return;
    }
    propage(i);
    int mid = ((deb + fin) >> 1);
    update(i*2, deb, mid, l, r, add);
    update(i*2+1, mid, fin, l, r, add);
    upd(i);
}*/

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> d;
    for(int i = 0; i < n + m; i++)
        cin >> a[i];
    for(int i = 0; i < n + m; i++) {
        sort(a, a + i + 1);
        int maxi = -INF, mini = INF;
        for(int j = 0; j <= i; j++) {
            maxi = max(maxi, a[j] - j * d);
            mini = min(mini, a[j] - j * d);
        }
        if(i >= n) {
            int diff = maxi - mini;
            if(diff % 2 == 1) cout << diff / 2 << ".5 ";
            else cout << diff / 2 << ' ';
        }
    }
    cout << '\n';
    /*
    for(int i = 0; i < n + m; i++) {
        cin >> a[i];
        pii[i].first = a[i];
        pii[i].second = i;
    }
    sort(pii, pii + n + m);
    for(int i = 0; i < n + m; i++)
        id[pii[i].second] = i;

    for(int i = 0; i < n + m; i++) {
        addNew(1, 0, M, id[i], a[i]);
        update(1, 0, M, id[i]+1, M, -d);
        if(i >= n) {
            int diff = node[1].maxi - node[1].mini;
            if(diff % 2 == 1) cout << diff / 2 << ".5 ";
            else cout << diff / 2 << ' ';
        }
    }
    cout << '\n';*/
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1570 ms 2076 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 1570 ms 2076 KB Time limit exceeded
2 Halted 0 ms 0 KB -