oj.uz

답안 #104140

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104140 2019-04-04T08:09:48 Z naoai 벽 (IOI14_wall) C++14
100 / 100
 953 ms 107056 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e6;
const int inf = 1 << 30;

static int v[nmax + 1];

struct str {
    int mn, mx;

    str () {
        mn = inf;
        mx = -inf;
    }
} aint[4 * nmax + 1];

void propaga (int nod) {
    for (int i = 0; i < 2; ++ i) {
        aint[2 * nod + i].mx = min(aint[2 * nod + i].mx, aint[nod].mn);
        aint[2 * nod + i].mn = min(aint[2 * nod + i].mn, aint[nod].mn);

        aint[2 * nod + i].mx = max(aint[2 * nod + i].mx, aint[nod].mx);
        aint[2 * nod + i].mn = max(aint[2 * nod + i].mn, aint[nod].mx);
    }

    aint[nod] = str();
}

void update_max (int nod, int x, int y, int st, int dr, int val) {
    if (st <= x && y <= dr) {
        aint[nod].mx = max(aint[nod].mx, val);
        aint[nod].mn = max(aint[nod].mn, val);
        return ;
    }

    propaga(nod);

    int mij = (x + y) / 2;
    if (st <= mij)
        update_max(2 * nod, x, mij, st, dr, val);
    if (mij < dr)
        update_max(2 * nod + 1, mij + 1, y, st, dr, val);
}

void update_min (int nod, int x, int y, int st, int dr, int val) {
    if (st <= x && y <= dr) {
        aint[nod].mx = min(aint[nod].mx, val);
        aint[nod].mn = min(aint[nod].mn, val);
        return ;
    }

    propaga(nod);

    int mij = (x + y) / 2;
    if (st <= mij)
        update_min(2 * nod, x, mij, st, dr, val);
    if (mij < dr)
        update_min(2 * nod + 1, mij + 1, y, st, dr, val);
}

void dfs (int nod, int x, int y) {
    if (x == y) {
        v[x] = max(aint[nod].mx, min(0, aint[nod].mn));
        return ;
    }

    propaga(nod);

    int mij = (x + y) / 2;
    dfs(2 * nod, x, mij);
    dfs(2 * nod + 1, mij + 1, y);
}

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)
            update_max(1, 0, n - 1, left[i], right[i], height[i]);
        else
            update_min(1, 0, n - 1, left[i], right[i], height[i]);
    }

    dfs(1, 0, n - 1);

    for (int i = 0; i < n; ++ i)
        finalHeight[i] = v[i];
    return;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 62968 KB Output is correct
2 Correct 58 ms 63096 KB Output is correct
3 Correct 57 ms 62968 KB Output is correct
4 Correct 62 ms 63264 KB Output is correct
5 Correct 61 ms 63224 KB Output is correct
6 Correct 67 ms 63224 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 62968 KB Output is correct
2 Correct 243 ms 71168 KB Output is correct
3 Correct 251 ms 66908 KB Output is correct
4 Correct 664 ms 72304 KB Output is correct
5 Correct 470 ms 72896 KB Output is correct
6 Correct 398 ms 72724 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 62968 KB Output is correct
2 Correct 59 ms 62956 KB Output is correct
3 Correct 59 ms 62968 KB Output is correct
4 Correct 63 ms 63224 KB Output is correct
5 Correct 64 ms 63224 KB Output is correct
6 Correct 74 ms 63224 KB Output is correct
7 Correct 55 ms 62968 KB Output is correct
8 Correct 260 ms 71288 KB Output is correct
9 Correct 286 ms 66776 KB Output is correct
10 Correct 654 ms 72392 KB Output is correct
11 Correct 389 ms 72696 KB Output is correct
12 Correct 398 ms 72696 KB Output is correct
13 Correct 55 ms 62968 KB Output is correct
14 Correct 233 ms 71160 KB Output is correct
15 Correct 95 ms 63992 KB Output is correct
16 Correct 609 ms 72440 KB Output is correct
17 Correct 344 ms 72388 KB Output is correct
18 Correct 401 ms 72568 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 62912 KB Output is correct
2 Correct 73 ms 63052 KB Output is correct
3 Correct 67 ms 62968 KB Output is correct
4 Correct 65 ms 63220 KB Output is correct
5 Correct 66 ms 63196 KB Output is correct
6 Correct 70 ms 63180 KB Output is correct
7 Correct 68 ms 62968 KB Output is correct
8 Correct 273 ms 71196 KB Output is correct
9 Correct 296 ms 66824 KB Output is correct
10 Correct 752 ms 72184 KB Output is correct
11 Correct 471 ms 72696 KB Output is correct
12 Correct 399 ms 72752 KB Output is correct
13 Correct 72 ms 62968 KB Output is correct
14 Correct 241 ms 71160 KB Output is correct
15 Correct 110 ms 63992 KB Output is correct
16 Correct 718 ms 72540 KB Output is correct
17 Correct 405 ms 72444 KB Output is correct
18 Correct 395 ms 72552 KB Output is correct
19 Correct 839 ms 97140 KB Output is correct
20 Correct 819 ms 104556 KB Output is correct
21 Correct 875 ms 107056 KB Output is correct
22 Correct 792 ms 104536 KB Output is correct
23 Correct 942 ms 104592 KB Output is correct
24 Correct 828 ms 104568 KB Output is correct
25 Correct 879 ms 104716 KB Output is correct
26 Correct 888 ms 107048 KB Output is correct
27 Correct 849 ms 106960 KB Output is correct
28 Correct 804 ms 104696 KB Output is correct
29 Correct 820 ms 104548 KB Output is correct
30 Correct 953 ms 104532 KB Output is correct