oj.uz

Submission #774022

# Submission time Handle Problem Language Result Execution time Memory
774022 2023-07-05T11:05:23 Z danikoynov Wall (IOI14_wall) C++14
100 / 100
 798 ms 159332 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_min(int root, int val)
{
    if (tree[root].max1 <= val)
        return;
        tree[root].max1 = min(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_min(int, int)':
wall.cpp:81:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   81 |     if (tree[root].max1 <= val)
      |     ^~
wall.cpp:83:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   83 |         tree[root].max1 = min(tree[root].max1, val);
      |         ^~~~
wall.cpp: In function 'void push_max(int, int)':
wall.cpp:99:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   99 |     if (val <= tree[root].min1)
      |     ^~
wall.cpp:102:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  102 |         tree[root].min1 = val;
      |         ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 125516 KB Output is correct
2 Correct 48 ms 125516 KB Output is correct
3 Correct 48 ms 125504 KB Output is correct
4 Correct 51 ms 125676 KB Output is correct
5 Correct 53 ms 125692 KB Output is correct
6 Correct 59 ms 125684 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 125504 KB Output is correct
2 Correct 157 ms 133272 KB Output is correct
3 Correct 103 ms 128972 KB Output is correct
4 Correct 186 ms 134264 KB Output is correct
5 Correct 194 ms 134788 KB Output is correct
6 Correct 234 ms 134824 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 51 ms 125524 KB Output is correct
3 Correct 51 ms 125492 KB Output is correct
4 Correct 56 ms 125748 KB Output is correct
5 Correct 55 ms 125644 KB Output is correct
6 Correct 54 ms 125620 KB Output is correct
7 Correct 51 ms 125412 KB Output is correct
8 Correct 160 ms 133360 KB Output is correct
9 Correct 108 ms 128972 KB Output is correct
10 Correct 187 ms 134256 KB Output is correct
11 Correct 201 ms 134872 KB Output is correct
12 Correct 240 ms 134792 KB Output is correct
13 Correct 52 ms 125492 KB Output is correct
14 Correct 161 ms 133356 KB Output is correct
15 Correct 85 ms 126204 KB Output is correct
16 Correct 603 ms 134536 KB Output is correct
17 Correct 379 ms 134604 KB Output is correct
18 Correct 354 ms 134572 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 125516 KB Output is correct
2 Correct 52 ms 125516 KB Output is correct
3 Correct 52 ms 125460 KB Output is correct
4 Correct 57 ms 125644 KB Output is correct
5 Correct 56 ms 125640 KB Output is correct
6 Correct 54 ms 125700 KB Output is correct
7 Correct 50 ms 125428 KB Output is correct
8 Correct 156 ms 133328 KB Output is correct
9 Correct 106 ms 128876 KB Output is correct
10 Correct 192 ms 134268 KB Output is correct
11 Correct 196 ms 134872 KB Output is correct
12 Correct 235 ms 134824 KB Output is correct
13 Correct 51 ms 125424 KB Output is correct
14 Correct 165 ms 133308 KB Output is correct
15 Correct 83 ms 126160 KB Output is correct
16 Correct 595 ms 134532 KB Output is correct
17 Correct 362 ms 134536 KB Output is correct
18 Correct 356 ms 134536 KB Output is correct
19 Correct 728 ms 159240 KB Output is correct
20 Correct 726 ms 156808 KB Output is correct
21 Correct 736 ms 159240 KB Output is correct
22 Correct 731 ms 156788 KB Output is correct
23 Correct 750 ms 156796 KB Output is correct
24 Correct 784 ms 156812 KB Output is correct
25 Correct 798 ms 156764 KB Output is correct
26 Correct 747 ms 159208 KB Output is correct
27 Correct 742 ms 159332 KB Output is correct
28 Correct 765 ms 156780 KB Output is correct
29 Correct 733 ms 156804 KB Output is correct
30 Correct 730 ms 156736 KB Output is correct