oj.uz

Submission #600410

# Submission time Handle Problem Language Result Execution time Memory
600410 2022-07-20T20:19:38 Z PiejanVDC Wall (IOI14_wall) C++17
100 / 100
 1474 ms 193276 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

/*
minA = min(min1, min2)
minA = max(minA, max2)
maxA = max(max1, max2)
maxA = min(maxA, min2)
*/

const int mxN = (int)2e7+5;

vector<int>mn(mxN, INT_MAX);
vector<int>mx(mxN, INT_MIN);

int l,r;
int MX, MN;

void reset(int p) {
    mn[p] = INT_MAX;
    mx[p] = INT_MIN;
}

void push(int mn_, int mx_, int p) {
    mn[p] = min(mn[p], mn_);
    mn[p] = max(mn[p], mx_);
    mx[p] = max(mx[p], mx_);
    mx[p] = min(mx[p], mn_);
}

void update(int i, int j, int p) {
    if(i > r || j < l)
        return;
    if(i >= l && j <= r) {
        mn[p] = min(mn[p], MN);
        mn[p] = max(mn[p], MX);
        mx[p] = max(mx[p], MX);
        mx[p] = min(mx[p], MN);
        return;
    }
    int mid = (i+j)/2;
    push(mn[p], mx[p], 2*p);
    push(mn[p], mx[p], 2*p+1);
    reset(p);
    update(i, mid, 2*p);
    update(mid+1, j, 2*p+1);
}

int query(int i, int j, int p) {
    if(i >= l && j <= r) {
        return max(0, mx[p]);
    }
    int mid = (i+j)/2;
    push(mn[p], mx[p], 2*p);
    push(mn[p], mx[p], 2*p+1);
    reset(p);
    if(l <= mid)
        return query(i, mid, 2*p);
    return query(mid+1, j, 2*p+1);
}

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) {
            MX = height[i];
            MN = INT_MAX;
            l = left[i];
            r = right[i];
            update(0, n-1, 1);
        } else {
            MX = INT_MIN;
            MN = height[i];
            l = left[i];
            r = right[i];
            update(0, n-1, 1);
        }
    }
    for(int i = 0 ; i < n ; i++) {
        l = i, r = i;
        finalHeight[i] = query(0, n-1, 1);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 156876 KB Output is correct
2 Correct 67 ms 156876 KB Output is correct
3 Correct 69 ms 156864 KB Output is correct
4 Correct 91 ms 156952 KB Output is correct
5 Correct 75 ms 156904 KB Output is correct
6 Correct 74 ms 156972 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 156832 KB Output is correct
2 Correct 191 ms 164656 KB Output is correct
3 Correct 237 ms 160192 KB Output is correct
4 Correct 557 ms 165204 KB Output is correct
5 Correct 405 ms 165692 KB Output is correct
6 Correct 405 ms 165720 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 156748 KB Output is correct
2 Correct 69 ms 156888 KB Output is correct
3 Correct 68 ms 156812 KB Output is correct
4 Correct 89 ms 156916 KB Output is correct
5 Correct 72 ms 156948 KB Output is correct
6 Correct 72 ms 156944 KB Output is correct
7 Correct 66 ms 156748 KB Output is correct
8 Correct 188 ms 164620 KB Output is correct
9 Correct 241 ms 160168 KB Output is correct
10 Correct 548 ms 165328 KB Output is correct
11 Correct 413 ms 165672 KB Output is correct
12 Correct 407 ms 165756 KB Output is correct
13 Correct 98 ms 156748 KB Output is correct
14 Correct 195 ms 164688 KB Output is correct
15 Correct 116 ms 157472 KB Output is correct
16 Correct 593 ms 165444 KB Output is correct
17 Correct 459 ms 165472 KB Output is correct
18 Correct 390 ms 165460 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 156864 KB Output is correct
2 Correct 77 ms 156896 KB Output is correct
3 Correct 65 ms 156808 KB Output is correct
4 Correct 79 ms 156972 KB Output is correct
5 Correct 77 ms 157004 KB Output is correct
6 Correct 76 ms 156924 KB Output is correct
7 Correct 74 ms 156776 KB Output is correct
8 Correct 201 ms 164576 KB Output is correct
9 Correct 255 ms 160204 KB Output is correct
10 Correct 584 ms 165200 KB Output is correct
11 Correct 407 ms 165712 KB Output is correct
12 Correct 395 ms 165668 KB Output is correct
13 Correct 80 ms 156748 KB Output is correct
14 Correct 257 ms 164584 KB Output is correct
15 Correct 102 ms 157480 KB Output is correct
16 Correct 600 ms 165508 KB Output is correct
17 Correct 387 ms 165460 KB Output is correct
18 Correct 434 ms 165464 KB Output is correct
19 Correct 1391 ms 182772 KB Output is correct
20 Correct 1419 ms 190824 KB Output is correct
21 Correct 1430 ms 193228 KB Output is correct
22 Correct 1446 ms 190764 KB Output is correct
23 Correct 1469 ms 190696 KB Output is correct
24 Correct 1406 ms 190768 KB Output is correct
25 Correct 1474 ms 190692 KB Output is correct
26 Correct 1404 ms 193276 KB Output is correct
27 Correct 1473 ms 193244 KB Output is correct
28 Correct 1380 ms 190712 KB Output is correct
29 Correct 1340 ms 190780 KB Output is correct
30 Correct 1394 ms 190656 KB Output is correct