oj.uz

Submission #774015

# Submission time Handle Problem Language Result Execution time Memory
774015 2023-07-05T11:02:07 Z danikoynov Wall (IOI14_wall) C++14
100 / 100
 811 ms 169756 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 10;
struct node
{
    int max1, max2;
    int min1, min2;

    node()
    {
        max1 = 0;
        max2 = -inf;
        min1 = 0;
        min2 = inf;
    }
};

node merge_node(node lf, node rf)
{
    node nd;
    if (lf.max1 == rf.max1)
    {
        nd.max1 = lf.max1;
        nd.max2 = max(lf.max2, rf.max2);
    }
    else if (lf.max1 > rf.max1)
    {
        nd.max1 = lf.max1;
        nd.max2 = max(lf.max2, rf.max1);
    }
    else if (lf.max1 < rf.max1)
    {
        nd.max1 = rf.max1;
        nd.max2 = max(lf.max1, rf.max2);
    }

    if (lf.min1 == rf.min1)
    {
        nd.min1 = lf.min1;
        nd.min2 = min(lf.min2, rf.min2);
    }
    else if (lf.min1 < rf.min1)
    {
        nd.min1 = lf.min1;
        nd.min2 = min(lf.min2, rf.min1);
    }
    else if (lf.min1 > rf.min1)
    {
        nd.min1 = rf.min1;
        nd.min2 = min(lf.min1, rf.min2);
    }

    return nd;
}

const int maxn = 2e6 + 10;

node tree[4 * maxn];

void push_min(int root, int val)
{
    if (val >= tree[root].max1)
        return;
    tree[root].max1 = val;

    if (tree[root].min1 >= val)
    {
        tree[root].min1 = val;
        tree[root].min2 = inf;
    }
    else if (tree[root].min2 > val)
    {
        tree[root].min2 = val;
    }
}

void push_max(int root, int val)
{
    if (val <= tree[root].min1)
        return;

        tree[root].min1 = val;
    if (tree[root].max1 <= val)
    {
        tree[root].max1 = val;
        tree[root].max2 = -inf;
    }
    else if (tree[root].max2 < val)
    {
        tree[root].max2 = val;
    }
}

void propagate(int root, int left, int right)
{
    if (left != right)
    {
        push_max(root * 2, tree[root].min1);
        push_max(root * 2 + 1, tree[root].min1);

        push_min(root * 2, tree[root].max1);
        push_min(root * 2 + 1, tree[root].max1);
    }
}

void update_min(int root, int left, int right, int qleft, int qright, int val)
{
    if (left > qright || right < qleft || tree[root].max1 <= val)
        return;

    if (left >= qleft && right <= qright && tree[root].max2 < val)
    {
        ///cout << "left " << left << " " << right << " " << tree[root].max1 << " " << tree[root].max2 << endl;
        push_min(root, val);

        return;
    }

    propagate(root, left, right);
    int mid = (left + right) / 2;
    update_min(root * 2, left, mid, qleft, qright, val);
    update_min(root * 2 + 1, mid + 1, right, qleft, qright, val);
    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

void update_max(int root, int left, int right, int qleft, int qright, int val)
{
    if (left > qright || right < qleft || tree[root].min1 >= val)
        return;

    if (left >= qleft && right <= qright && tree[root].min2 > val)
    {
        push_max(root, val);
        ///cout << root << " : " << left << " : " << right << endl;
        ///cout << tree[root].min1 << endl;
        //cout << tree[root].max1 << endl;
        return;
    }

    propagate(root, left, right);
    int mid = (left + right) / 2;

    update_max(root * 2, left, mid, qleft, qright, val);
    update_max(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

int arr[maxn];

void dfs(int root, int left, int right)
{
    ///cout << "dfs " << root << " " << left << " " << right << " " << tree[root].min1 << " " << tree[root].max1 << endl;
    if (left == right)
    {
        arr[left] = tree[root].max1;
        return;
    }
    propagate(root, left, right);
    int mid = (left + right) / 2;
    dfs(root * 2, left, mid);
    dfs(root * 2 + 1, mid + 1, right);
}
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] = arr[i];
    return;
}

Compilation message

wall.cpp: In function 'void push_max(int, int)':
wall.cpp:81:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   81 |     if (val <= tree[root].min1)
      |     ^~
wall.cpp:84:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   84 |         tree[root].min1 = val;
      |         ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 125516 KB Output is correct
2 Correct 49 ms 125572 KB Output is correct
3 Correct 50 ms 125540 KB Output is correct
4 Correct 61 ms 125756 KB Output is correct
5 Correct 54 ms 125828 KB Output is correct
6 Correct 59 ms 125904 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 125432 KB Output is correct
2 Correct 159 ms 133312 KB Output is correct
3 Correct 114 ms 128880 KB Output is correct
4 Correct 191 ms 143936 KB Output is correct
5 Correct 209 ms 145020 KB Output is correct
6 Correct 241 ms 143400 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 125516 KB Output is correct
2 Correct 52 ms 125608 KB Output is correct
3 Correct 52 ms 125464 KB Output is correct
4 Correct 57 ms 125728 KB Output is correct
5 Correct 56 ms 125772 KB Output is correct
6 Correct 55 ms 125764 KB Output is correct
7 Correct 51 ms 125436 KB Output is correct
8 Correct 161 ms 139100 KB Output is correct
9 Correct 108 ms 132684 KB Output is correct
10 Correct 198 ms 143944 KB Output is correct
11 Correct 244 ms 144996 KB Output is correct
12 Correct 241 ms 143336 KB Output is correct
13 Correct 51 ms 125472 KB Output is correct
14 Correct 166 ms 139120 KB Output is correct
15 Correct 83 ms 126788 KB Output is correct
16 Correct 644 ms 144224 KB Output is correct
17 Correct 372 ms 143564 KB Output is correct
18 Correct 374 ms 143564 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 125528 KB Output is correct
2 Correct 60 ms 125592 KB Output is correct
3 Correct 53 ms 125512 KB Output is correct
4 Correct 58 ms 125820 KB Output is correct
5 Correct 56 ms 125816 KB Output is correct
6 Correct 56 ms 125772 KB Output is correct
7 Correct 53 ms 125428 KB Output is correct
8 Correct 164 ms 139168 KB Output is correct
9 Correct 112 ms 132684 KB Output is correct
10 Correct 193 ms 143884 KB Output is correct
11 Correct 213 ms 144940 KB Output is correct
12 Correct 239 ms 143368 KB Output is correct
13 Correct 54 ms 125504 KB Output is correct
14 Correct 166 ms 139152 KB Output is correct
15 Correct 84 ms 126892 KB Output is correct
16 Correct 608 ms 144156 KB Output is correct
17 Correct 366 ms 143572 KB Output is correct
18 Correct 364 ms 143568 KB Output is correct
19 Correct 734 ms 169648 KB Output is correct
20 Correct 778 ms 167240 KB Output is correct
21 Correct 750 ms 169676 KB Output is correct
22 Correct 789 ms 167212 KB Output is correct
23 Correct 737 ms 167236 KB Output is correct
24 Correct 742 ms 167236 KB Output is correct
25 Correct 735 ms 167188 KB Output is correct
26 Correct 794 ms 169756 KB Output is correct
27 Correct 811 ms 169740 KB Output is correct
28 Correct 771 ms 167212 KB Output is correct
29 Correct 741 ms 167240 KB Output is correct
30 Correct 743 ms 167132 KB Output is correct