oj.uz

Submission #102747

# Submission time Handle Problem Language Result Execution time Memory
102747 2019-03-27T11:53:12 Z naoai Wall (IOI14_wall) C++14
32 / 100
 403 ms 20968 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];
static int aint[4 * nmax + 1];

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

    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] = min(aint[nod], val);
        return ;
    }

    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 build (int nod, int x, int y) {
    aint[nod] = inf;
    if (x == y)
        return ;

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

void dfs_min (int nod, int x, int y, int val = inf) {
    val = min(val, aint[nod]);

    if (x == y) {
        v[x] = min(val, v[x]);
        return ;
    }

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

void dfs_max (int nod, int x, int y, int val = -inf) {
    val = max(val, aint[nod]);

    if (x == y) {
        v[x] = max(val, v[x]);
        return ;
    }

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


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    if (n <= 10000 && k <= 5000) {
        for (int i = 0; i < k; ++ i) {
            for (int j = left[i]; j <= right[i]; ++ j) {
                if (op[i] == 1)
                    v[j] = max(v[j], height[i]);
                else
                    v[j] = min(v[j], height[i]);
            }
        }
    } else {
        int ind = 0;
        while (ind < k && op[ind] == 1) {
            update_max(1, 0, n - 1, left[ind], right[ind], height[ind]);
            ++ ind;
        }

        dfs_max(1, 0, n - 1);
        build(1, 0, n - 1);

        while (ind < k) {
            update_min(1, 0, n - 1, left[ind], right[ind], height[ind]);
            ++ ind;
        }
        dfs_min(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 2 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 3 ms 420 KB Output is correct
4 Correct 21 ms 640 KB Output is correct
5 Correct 22 ms 640 KB Output is correct
6 Correct 33 ms 632 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 189 ms 14132 KB Output is correct
3 Correct 146 ms 7868 KB Output is correct
4 Correct 403 ms 19816 KB Output is correct
5 Correct 280 ms 20880 KB Output is correct
6 Correct 243 ms 19192 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 27 ms 640 KB Output is correct
5 Correct 25 ms 640 KB Output is correct
6 Correct 26 ms 640 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 173 ms 14044 KB Output is correct
9 Correct 150 ms 7864 KB Output is correct
10 Correct 369 ms 19904 KB Output is correct
11 Correct 237 ms 20856 KB Output is correct
12 Correct 242 ms 19320 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Incorrect 151 ms 14044 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 28 ms 632 KB Output is correct
5 Correct 22 ms 640 KB Output is correct
6 Correct 29 ms 632 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 176 ms 14196 KB Output is correct
9 Correct 179 ms 7932 KB Output is correct
10 Correct 352 ms 19804 KB Output is correct
11 Correct 276 ms 20968 KB Output is correct
12 Correct 221 ms 19280 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Incorrect 164 ms 14044 KB Output isn't correct
15 Halted 0 ms 0 KB -