oj.uz

Submission #1030979

# Submission time Handle Problem Language Result Execution time Memory
1030979 2024-07-22T13:12:28 Z ArthuroWich Wall (IOI14_wall) C++17
100 / 100
 711 ms 86868 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int segmin[4*2000005], segmax[4*2000005], lazy[4*2000005];
void lazypropagate(int n, int l, int r) {
    if (lazy[n] != -1) {
        segmin[n] = lazy[n];
        segmax[n] = lazy[n];
        if (l != r) {
            lazy[2*n] = lazy[n];
            lazy[2*n+1] = lazy[n];
        }
        lazy[n] = -1;
    }
}
void update1(int n, int l, int r, int a, int b, int h) {
    lazypropagate(n, l, r);
    if (b < l || r < a || segmin[n] >= h) {
        return;
    }
    if (a <= l && r <= b && segmax[n] < h) {
        lazy[n] = h;
        lazypropagate(n, l, r);
    } else { 
        int m = (l+r)/2;
        update1(2*n, l, m, a, b, h);
        update1(2*n+1, m+1, r, a, b, h);
        segmax[n] = max(segmax[2*n], segmax[2*n+1]);
        segmin[n] = min(segmin[2*n], segmin[2*n+1]);
    }
}
void update2(int n, int l, int r, int a, int b, int h) {
    lazypropagate(n, l, r);
    if (b < l || r < a || segmax[n] <= h) {
        return;
    }
    if (a <= l && r <= b && segmin[n] > h) {
        lazy[n] = h;
        lazypropagate(n, l, r);
    } else {
        int m = (l+r)/2;
        update2(2*n, l, m, a, b, h);
        update2(2*n+1, m+1, r, a, b, h);
        segmax[n] = max(segmax[2*n], segmax[2*n+1]);
        segmin[n] = min(segmin[2*n], segmin[2*n+1]);
    }
}
int query(int n, int l, int r, int i) {
    lazypropagate(n, l, r);
    if (l == r) {
        return segmax[n];
    } else {
        int m = (l+r)/2;
        if (l <= i && i <= m) {
            return query(2*n, l, m, i);
        } else {
            return query(2*n+1, m+1, r, i);
        }
    }
} 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            update1(1, 0, n-1, left[i], right[i], height[i]);
        } else {
            update2(1, 0, n-1, left[i], right[i], height[i]);
        }
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = query(1, 0, n-1, i);
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 2632 KB Output is correct
3 Correct 1 ms 2504 KB Output is correct
4 Correct 4 ms 2904 KB Output is correct
5 Correct 4 ms 2904 KB Output is correct
6 Correct 4 ms 3020 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 96 ms 16008 KB Output is correct
3 Correct 47 ms 10060 KB Output is correct
4 Correct 118 ms 22356 KB Output is correct
5 Correct 118 ms 23636 KB Output is correct
6 Correct 135 ms 22868 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 4 ms 4880 KB Output is correct
5 Correct 4 ms 2908 KB Output is correct
6 Correct 4 ms 2908 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 79 ms 15960 KB Output is correct
9 Correct 48 ms 10136 KB Output is correct
10 Correct 117 ms 22452 KB Output is correct
11 Correct 119 ms 23528 KB Output is correct
12 Correct 141 ms 21844 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 85 ms 16080 KB Output is correct
15 Correct 19 ms 3968 KB Output is correct
16 Correct 322 ms 22612 KB Output is correct
17 Correct 210 ms 22100 KB Output is correct
18 Correct 217 ms 23296 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 4 ms 4924 KB Output is correct
5 Correct 4 ms 2904 KB Output is correct
6 Correct 4 ms 2908 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 79 ms 16120 KB Output is correct
9 Correct 47 ms 10124 KB Output is correct
10 Correct 123 ms 22376 KB Output is correct
11 Correct 118 ms 24496 KB Output is correct
12 Correct 135 ms 21960 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 83 ms 15952 KB Output is correct
15 Correct 19 ms 4176 KB Output is correct
16 Correct 322 ms 22616 KB Output is correct
17 Correct 217 ms 22100 KB Output is correct
18 Correct 215 ms 22080 KB Output is correct
19 Correct 537 ms 86868 KB Output is correct
20 Correct 533 ms 84732 KB Output is correct
21 Correct 583 ms 86864 KB Output is correct
22 Correct 563 ms 84328 KB Output is correct
23 Correct 591 ms 84308 KB Output is correct
24 Correct 566 ms 83528 KB Output is correct
25 Correct 551 ms 83540 KB Output is correct
26 Correct 588 ms 86096 KB Output is correct
27 Correct 634 ms 86088 KB Output is correct
28 Correct 711 ms 83600 KB Output is correct
29 Correct 629 ms 84304 KB Output is correct
30 Correct 517 ms 84300 KB Output is correct