oj.uz

Submission #426091

# Submission time Handle Problem Language Result Execution time Memory
426091 2021-06-13T13:51:29 Z someone Wall (IOI14_wall) C++14
100 / 100
 860 ms 95808 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int deb, fin, a, b;
};

const int T = 21, M = 1 << T, N = 2*M, INF = 1e9;

Node node[N];

void applyOp(int i, int a, int b) {
    node[i].a = min(b, max(a, node[i].a));
    node[i].b = min(b, max(a, node[i].b));
}

void update(int i, int deb, int fin, int a, int b) {
    if(fin <= node[i].deb || node[i].fin <= deb)
        return;
    if(deb <= node[i].deb && node[i].fin <= fin) {
        applyOp(i, a, b);
        return;
    }
    applyOp(i*2, node[i].a, node[i].b);
    applyOp(i*2+1, node[i].a, node[i].b);

    node[i].a = -INF;
    node[i].b = INF;

    update(i*2, deb, fin, a, b);
    update(i*2+1, deb, fin, a, b);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i = 0; i < M; i++) {
        node[i + M].deb = i;
        node[i + M].fin = i+1;
    }
    for(int i = M-1; i > -1; i--) {
        node[i].deb = node[i*2].deb;
        node[i].fin = node[i*2+1].fin;
    }
    for(int i = 0; i < N; i++)
        node[i].a = -INF, node[i].b = INF;
    for(int i = 0; i < k; i++) {
        if(op[i] == 1)
            update(1, left[i], right[i]+1, height[i], INF);
        else
            update(1, left[i], right[i]+1, -INF, height[i]);
    }
    for(int i = 1; i < M; i++) {
        applyOp(i*2, node[i].a, node[i].b);
        applyOp(i*2+1, node[i].a, node[i].b);
    }
    for(int i = 0; i < n; i++)
        finalHeight[i] = min(node[i+M].b, max(node[i+M].a, 0));
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 65876 KB Output is correct
2 Correct 61 ms 65984 KB Output is correct
3 Correct 62 ms 65964 KB Output is correct
4 Correct 61 ms 66196 KB Output is correct
5 Correct 68 ms 66124 KB Output is correct
6 Correct 61 ms 66148 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 65932 KB Output is correct
2 Correct 383 ms 73784 KB Output is correct
3 Correct 265 ms 69284 KB Output is correct
4 Correct 662 ms 78140 KB Output is correct
5 Correct 425 ms 78660 KB Output is correct
6 Correct 429 ms 78020 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 65892 KB Output is correct
2 Correct 66 ms 65944 KB Output is correct
3 Correct 59 ms 65988 KB Output is correct
4 Correct 68 ms 66188 KB Output is correct
5 Correct 74 ms 66164 KB Output is correct
6 Correct 64 ms 66224 KB Output is correct
7 Correct 57 ms 65860 KB Output is correct
8 Correct 391 ms 76348 KB Output is correct
9 Correct 277 ms 71828 KB Output is correct
10 Correct 676 ms 78140 KB Output is correct
11 Correct 481 ms 78636 KB Output is correct
12 Correct 427 ms 78120 KB Output is correct
13 Correct 78 ms 65936 KB Output is correct
14 Correct 414 ms 76284 KB Output is correct
15 Correct 87 ms 67120 KB Output is correct
16 Correct 658 ms 78540 KB Output is correct
17 Correct 454 ms 78148 KB Output is correct
18 Correct 444 ms 78156 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 65880 KB Output is correct
2 Correct 68 ms 66028 KB Output is correct
3 Correct 66 ms 65936 KB Output is correct
4 Correct 68 ms 66112 KB Output is correct
5 Correct 66 ms 66104 KB Output is correct
6 Correct 67 ms 66148 KB Output is correct
7 Correct 61 ms 65860 KB Output is correct
8 Correct 390 ms 76300 KB Output is correct
9 Correct 256 ms 71768 KB Output is correct
10 Correct 631 ms 78160 KB Output is correct
11 Correct 438 ms 78672 KB Output is correct
12 Correct 423 ms 78020 KB Output is correct
13 Correct 55 ms 65860 KB Output is correct
14 Correct 395 ms 76344 KB Output is correct
15 Correct 95 ms 67124 KB Output is correct
16 Correct 714 ms 78440 KB Output is correct
17 Correct 430 ms 78164 KB Output is correct
18 Correct 435 ms 78276 KB Output is correct
19 Correct 856 ms 95808 KB Output is correct
20 Correct 794 ms 91856 KB Output is correct
21 Correct 794 ms 94168 KB Output is correct
22 Correct 823 ms 91716 KB Output is correct
23 Correct 845 ms 91864 KB Output is correct
24 Correct 821 ms 92316 KB Output is correct
25 Correct 840 ms 92100 KB Output is correct
26 Correct 860 ms 94700 KB Output is correct
27 Correct 832 ms 94688 KB Output is correct
28 Correct 829 ms 92144 KB Output is correct
29 Correct 813 ms 92208 KB Output is correct
30 Correct 841 ms 92112 KB Output is correct