oj.uz

Submission #102749

# Submission time Handle Problem Language Result Execution time Memory
102749 2019-03-27T11:55:38 Z naoai Wall (IOI14_wall) C++14
32 / 100
 3000 ms 19320 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, int val) {
    aint[nod] = val;
    if (x == y)
        return ;

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

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) {
            build(1, 0, n - 1, 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, inf);

            while (ind < k && op[ind] == 2) {
                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 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 31 ms 512 KB Output is correct
5 Correct 23 ms 512 KB Output is correct
6 Correct 22 ms 512 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 174 ms 8184 KB Output is correct
3 Correct 191 ms 3996 KB Output is correct
4 Correct 471 ms 10332 KB Output is correct
5 Correct 232 ms 10832 KB Output is correct
6 Correct 234 ms 10708 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 24 ms 512 KB Output is correct
5 Correct 33 ms 512 KB Output is correct
6 Correct 24 ms 512 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 154 ms 8184 KB Output is correct
9 Correct 193 ms 4072 KB Output is correct
10 Correct 449 ms 10360 KB Output is correct
11 Correct 262 ms 10820 KB Output is correct
12 Correct 295 ms 10744 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 201 ms 8316 KB Output is correct
15 Correct 2479 ms 2040 KB Output is correct
16 Execution timed out 3014 ms 19320 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 22 ms 512 KB Output is correct
5 Correct 23 ms 512 KB Output is correct
6 Correct 24 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 235 ms 8160 KB Output is correct
9 Correct 141 ms 4088 KB Output is correct
10 Correct 394 ms 10228 KB Output is correct
11 Correct 259 ms 10616 KB Output is correct
12 Correct 255 ms 10744 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 223 ms 8284 KB Output is correct
15 Correct 2593 ms 1892 KB Output is correct
16 Execution timed out 3015 ms 19192 KB Time limit exceeded
17 Halted 0 ms 0 KB -