oj.uz

Submission #104139

# Submission time Handle Problem Language Result Execution time Memory
104139 2019-04-04T08:08:05 Z naoai Wall (IOI14_wall) C++14
61 / 100
 626 ms 32972 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5;
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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 7 ms 3584 KB Output is correct
3 Correct 7 ms 3584 KB Output is correct
4 Correct 11 ms 3712 KB Output is correct
5 Correct 11 ms 3712 KB Output is correct
6 Correct 11 ms 3712 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3584 KB Output is correct
2 Correct 182 ms 17084 KB Output is correct
3 Correct 277 ms 10744 KB Output is correct
4 Correct 626 ms 21900 KB Output is correct
5 Correct 312 ms 22904 KB Output is correct
6 Correct 348 ms 21444 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 7 ms 3584 KB Output is correct
3 Correct 8 ms 3456 KB Output is correct
4 Correct 12 ms 3712 KB Output is correct
5 Correct 12 ms 3712 KB Output is correct
6 Correct 12 ms 3840 KB Output is correct
7 Correct 5 ms 3456 KB Output is correct
8 Correct 172 ms 17144 KB Output is correct
9 Correct 194 ms 10744 KB Output is correct
10 Correct 546 ms 21880 KB Output is correct
11 Correct 360 ms 22924 KB Output is correct
12 Correct 316 ms 21496 KB Output is correct
13 Correct 5 ms 3456 KB Output is correct
14 Correct 203 ms 17116 KB Output is correct
15 Correct 44 ms 4728 KB Output is correct
16 Correct 595 ms 22192 KB Output is correct
17 Correct 375 ms 21560 KB Output is correct
18 Correct 334 ms 21548 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 8 ms 3584 KB Output is correct
3 Correct 7 ms 3584 KB Output is correct
4 Correct 12 ms 3712 KB Output is correct
5 Correct 10 ms 3692 KB Output is correct
6 Correct 11 ms 3712 KB Output is correct
7 Correct 6 ms 3456 KB Output is correct
8 Correct 179 ms 17040 KB Output is correct
9 Correct 194 ms 10744 KB Output is correct
10 Correct 592 ms 22008 KB Output is correct
11 Correct 337 ms 23032 KB Output is correct
12 Correct 275 ms 21420 KB Output is correct
13 Correct 4 ms 3456 KB Output is correct
14 Correct 151 ms 17148 KB Output is correct
15 Correct 30 ms 4736 KB Output is correct
16 Correct 525 ms 22312 KB Output is correct
17 Correct 284 ms 21624 KB Output is correct
18 Correct 325 ms 21712 KB Output is correct
19 Runtime error 249 ms 32972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -