제출 #774024

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
774024		danikoynov	벽 (IOI14_wall)	C++14	100 / 100	902 ms	159244 KiB

wall

#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 != inf)
    {
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39