oj.uz

Submission #723356

# Submission time Handle Problem Language Result Execution time Memory
723356 2023-04-13T16:04:05 Z someone Measures (CEOI22_measures) C++14
100 / 100
 364 ms 26240 KB 
#include <bits/stdc++.h>
#define int long long
#define mid ((deb + fin) >> 1)
using namespace std;
    
const int M = 1 << 18, N = 2 * M, INF = 1e18 + 42;
    
struct Node {
    int mini, maxi, maxDiff, lazy, nb;
} node[N];
    
pair<int, int> pii[M];
int n, m, d, a[N], id[M];

inline void applyOp(int i, int add) {
    node[i].mini += add;
    node[i].maxi += add;
    node[i].lazy += add;
}
    
inline void upd(int i) {
    node[i].mini = INF;
    node[i].maxi = -INF;
    node[i].maxDiff = 0;
    for(int child : {i*2, i*2+1})
        if(node[child].nb) {
            node[i].mini = min(node[i].mini, node[child].mini);
            node[i].maxi = max(node[i].maxi, node[child].maxi);
            node[i].maxDiff = max(node[i].maxDiff, node[child].maxDiff);
        }
    if(node[i*2].nb && node[i*2+1].nb)
        node[i].maxDiff = max(node[i].maxDiff, node[i*2].maxi - node[i*2+1].mini);
}

inline void propage(int i) {
    applyOp(i*2, node[i].lazy);
    applyOp(i*2+1, node[i].lazy);
    node[i].lazy = 0;
}
    
void update(int i, int deb, int fin, int l, int r, int add, int nouv) {
    if(fin <= l || r <= deb) return;
    if(nouv == 0 && l <= deb && fin <= r) {
        applyOp(i, add);
        return;
    }
    if(nouv) node[i].nb++;
    if(fin - deb == 1 && deb == l) {
        node[i].mini += nouv;
        node[i].maxi += nouv;
        return;
    }
    propage(i);
    update(i*2, deb, mid, l, r, add, nouv);
    update(i*2+1, mid, fin, l, r, add, nouv);
    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];
        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++) {
        update(1, 0, M, id[i], id[i]+1, 0, a[i]);
        update(1, 0, M, id[i]+1, M, -d, 0);
        if(i >= n) {
            if(node[1].maxDiff % 2 == 1) cout << node[1].maxDiff / 2 << ".5 ";
            else cout << node[1].maxDiff / 2 << ' ';
        }
    }
    cout << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 271 ms 22220 KB Output is correct
10 Correct 304 ms 23104 KB Output is correct
11 Correct 220 ms 23008 KB Output is correct
12 Correct 247 ms 23144 KB Output is correct
13 Correct 192 ms 22980 KB Output is correct
14 Correct 211 ms 23024 KB Output is correct
15 Correct 263 ms 23104 KB Output is correct
16 Correct 241 ms 23044 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 24636 KB Output is correct
2 Correct 220 ms 25960 KB Output is correct
3 Correct 233 ms 25984 KB Output is correct
4 Correct 246 ms 23880 KB Output is correct
5 Correct 217 ms 25084 KB Output is correct
6 Correct 225 ms 24376 KB Output is correct
7 Correct 237 ms 25152 KB Output is correct
8 Correct 225 ms 23848 KB Output is correct
9 Correct 248 ms 23744 KB Output is correct
10 Correct 253 ms 26240 KB Output is correct
11 Correct 225 ms 24596 KB Output is correct
12 Correct 219 ms 25568 KB Output is correct
13 Correct 244 ms 23780 KB Output is correct
14 Correct 216 ms 25808 KB Output is correct
15 Correct 285 ms 25680 KB Output is correct
16 Correct 219 ms 23880 KB Output is correct
17 Correct 230 ms 25176 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 24636 KB Output is correct
2 Correct 220 ms 25960 KB Output is correct
3 Correct 233 ms 25984 KB Output is correct
4 Correct 246 ms 23880 KB Output is correct
5 Correct 217 ms 25084 KB Output is correct
6 Correct 225 ms 24376 KB Output is correct
7 Correct 237 ms 25152 KB Output is correct
8 Correct 225 ms 23848 KB Output is correct
9 Correct 248 ms 23744 KB Output is correct
10 Correct 253 ms 26240 KB Output is correct
11 Correct 225 ms 24596 KB Output is correct
12 Correct 219 ms 25568 KB Output is correct
13 Correct 244 ms 23780 KB Output is correct
14 Correct 216 ms 25808 KB Output is correct
15 Correct 285 ms 25680 KB Output is correct
16 Correct 219 ms 23880 KB Output is correct
17 Correct 230 ms 25176 KB Output is correct
18 Correct 333 ms 24216 KB Output is correct
19 Correct 340 ms 25896 KB Output is correct
20 Correct 251 ms 25976 KB Output is correct
21 Correct 290 ms 23968 KB Output is correct
22 Correct 269 ms 24332 KB Output is correct
23 Correct 270 ms 24196 KB Output is correct
24 Correct 306 ms 24688 KB Output is correct
25 Correct 213 ms 23736 KB Output is correct
26 Correct 364 ms 23724 KB Output is correct
27 Correct 354 ms 26240 KB Output is correct
28 Correct 278 ms 24300 KB Output is correct
29 Correct 319 ms 26056 KB Output is correct
30 Correct 243 ms 24084 KB Output is correct
31 Correct 244 ms 26088 KB Output is correct
32 Correct 265 ms 25932 KB Output is correct
33 Correct 311 ms 24172 KB Output is correct
34 Correct 273 ms 25340 KB Output is correct