oj.uz

Submission #723333

# Submission time Handle Problem Language Result Execution time Memory
723333 2023-04-13T15:45:08 Z someone Measures (CEOI22_measures) C++14
10 / 100
 1500 ms 2080 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, maxDiff = -INF;
            for(int j = 0; j <= i; j++) {
                maxi = max(maxi, a[j] - j * d);
                maxDiff = max(maxDiff, maxi - (a[j] - j * d));
            }
            if(i >= n) {
                if(maxDiff % 2 == 1) cout << maxDiff / 2 << ".5 ";
                else cout << maxDiff / 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 340 KB Output is correct
2 Correct 24 ms 340 KB Output is correct
3 Correct 16 ms 360 KB Output is correct
4 Correct 28 ms 340 KB Output is correct
5 Correct 22 ms 360 KB Output is correct
6 Correct 50 ms 340 KB Output is correct
7 Correct 62 ms 340 KB Output is correct
8 Correct 24 ms 356 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 340 KB Output is correct
2 Correct 24 ms 340 KB Output is correct
3 Correct 16 ms 360 KB Output is correct
4 Correct 28 ms 340 KB Output is correct
5 Correct 22 ms 360 KB Output is correct
6 Correct 50 ms 340 KB Output is correct
7 Correct 62 ms 340 KB Output is correct
8 Correct 24 ms 356 KB Output is correct
9 Execution timed out 1584 ms 1892 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 1557 ms 2080 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 1557 ms 2080 KB Time limit exceeded
2 Halted 0 ms 0 KB -