oj.uz

Submission #372359

# Submission time Handle Problem Language Result Execution time Memory
372359 2021-02-27T20:49:39 Z idk321 Wall (IOI14_wall) C++11
100 / 100
 1233 ms 69852 KB 
#include "wall.h"

#include <bits/stdc++.h>
using namespace std;

const int N = 2000005;
const int M = 1000000000;
int tree[4 * N][2];

void apply(int node, array<int, 2> make)
{
    if (tree[node][0] <= make[0])
    {
        tree[node][0] = max(make[0], tree[node][0]);
        tree[node][1] = max(min(make[1], tree[node][1]), tree[node][0]);
    } else
    {
        tree[node][1] = min(make[1], tree[node][1]);
        tree[node][0] = min(max(make[0], tree[node][0]), tree[node][1]);
    }

}

void push(int node)
{
    for (int i = 0; i <= 1; i++) apply(node * 2 + i, {tree[node][0], tree[node][1]});
    tree[node][0] = -1;
    tree[node][1] = M;
}

void ins(int from, int to, const array<int, 2>& make, int a, int b, int node)
{
    if (from <= a && b <= to)
    {
        apply(node, make);
        return;
    }

    int mid = (a + b) / 2;
    push(node);
    if (from <= mid) ins(from, to, make, a, mid, node * 2);
    if (to > mid) ins(from, to, make, mid + 1, b, node * 2 +1);
}

int getRes(int i, int a, int b, int node)
{
    if (a == b) return tree[node][0];

    int mid = (a + b) / 2;
    push(node);
    if (i <= mid) return getRes(i, a, mid, node * 2);
    return getRes(i, mid + 1, b, node * 2 + 1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < k; i++)
    {
        int a = left[i];
        int b = right[i];
        array<int, 2> make = {};
        make[0] = -1;
        make[1] = M;
        if (op[i] == 1)
        {
            make[0] = height[i];
        } else make[1] = height[i];
        ins(a, b, make, 0, n - 1, 1);
    }

    for (int i = 0; i < n; i++) finalHeight[i] = getRes(i, 0, n - 1, 1);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 8 ms 876 KB Output is correct
5 Correct 7 ms 876 KB Output is correct
6 Correct 7 ms 876 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 184 ms 13932 KB Output is correct
3 Correct 213 ms 8044 KB Output is correct
4 Correct 539 ms 20460 KB Output is correct
5 Correct 349 ms 21484 KB Output is correct
6 Correct 336 ms 20012 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 8 ms 876 KB Output is correct
5 Correct 7 ms 876 KB Output is correct
6 Correct 7 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 170 ms 13932 KB Output is correct
9 Correct 214 ms 8044 KB Output is correct
10 Correct 524 ms 20588 KB Output is correct
11 Correct 348 ms 21548 KB Output is correct
12 Correct 326 ms 20076 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 188 ms 14008 KB Output is correct
15 Correct 36 ms 2048 KB Output is correct
16 Correct 602 ms 20716 KB Output is correct
17 Correct 340 ms 20204 KB Output is correct
18 Correct 336 ms 20108 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 9 ms 876 KB Output is correct
5 Correct 7 ms 876 KB Output is correct
6 Correct 7 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 162 ms 13932 KB Output is correct
9 Correct 221 ms 8044 KB Output is correct
10 Correct 522 ms 20460 KB Output is correct
11 Correct 351 ms 21484 KB Output is correct
12 Correct 326 ms 20000 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 162 ms 13932 KB Output is correct
15 Correct 36 ms 2028 KB Output is correct
16 Correct 620 ms 20716 KB Output is correct
17 Correct 340 ms 20076 KB Output is correct
18 Correct 339 ms 20204 KB Output is correct
19 Correct 1198 ms 69732 KB Output is correct
20 Correct 1214 ms 67236 KB Output is correct
21 Correct 1233 ms 69852 KB Output is correct
22 Correct 1209 ms 67180 KB Output is correct
23 Correct 1198 ms 67308 KB Output is correct
24 Correct 1211 ms 67180 KB Output is correct
25 Correct 1203 ms 67180 KB Output is correct
26 Correct 1208 ms 69740 KB Output is correct
27 Correct 1229 ms 69624 KB Output is correct
28 Correct 1203 ms 67052 KB Output is correct
29 Correct 1214 ms 67348 KB Output is correct
30 Correct 1204 ms 67120 KB Output is correct