oj.uz

답안 #774024

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
774024 2023-07-05T11:06:41 Z danikoynov 벽 (IOI14_wall) C++14
100 / 100
 902 ms 159244 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 != 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;
}

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 125452 KB Output is correct
2 Correct 52 ms 125552 KB Output is correct
3 Correct 49 ms 125516 KB Output is correct
4 Correct 57 ms 125620 KB Output is correct
5 Correct 52 ms 125632 KB Output is correct
6 Correct 52 ms 125708 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 125436 KB Output is correct
2 Correct 160 ms 133264 KB Output is correct
3 Correct 107 ms 128968 KB Output is correct
4 Correct 185 ms 134340 KB Output is correct
5 Correct 190 ms 134772 KB Output is correct
6 Correct 233 ms 134784 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 125420 KB Output is correct
2 Correct 57 ms 125544 KB Output is correct
3 Correct 56 ms 125536 KB Output is correct
4 Correct 54 ms 125696 KB Output is correct
5 Correct 66 ms 125664 KB Output is correct
6 Correct 51 ms 125680 KB Output is correct
7 Correct 47 ms 125528 KB Output is correct
8 Correct 170 ms 133272 KB Output is correct
9 Correct 123 ms 128988 KB Output is correct
10 Correct 197 ms 134276 KB Output is correct
11 Correct 225 ms 134860 KB Output is correct
12 Correct 244 ms 134868 KB Output is correct
13 Correct 49 ms 125464 KB Output is correct
14 Correct 152 ms 133252 KB Output is correct
15 Correct 102 ms 126152 KB Output is correct
16 Correct 705 ms 134536 KB Output is correct
17 Correct 361 ms 134596 KB Output is correct
18 Correct 432 ms 134536 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 125516 KB Output is correct
2 Correct 58 ms 125568 KB Output is correct
3 Correct 50 ms 125472 KB Output is correct
4 Correct 60 ms 125644 KB Output is correct
5 Correct 60 ms 125644 KB Output is correct
6 Correct 59 ms 125688 KB Output is correct
7 Correct 54 ms 125528 KB Output is correct
8 Correct 149 ms 133292 KB Output is correct
9 Correct 117 ms 128984 KB Output is correct
10 Correct 189 ms 134284 KB Output is correct
11 Correct 216 ms 134856 KB Output is correct
12 Correct 242 ms 134876 KB Output is correct
13 Correct 55 ms 125424 KB Output is correct
14 Correct 173 ms 133332 KB Output is correct
15 Correct 98 ms 126156 KB Output is correct
16 Correct 657 ms 134540 KB Output is correct
17 Correct 359 ms 134536 KB Output is correct
18 Correct 373 ms 134536 KB Output is correct
19 Correct 803 ms 159240 KB Output is correct
20 Correct 902 ms 156728 KB Output is correct
21 Correct 793 ms 159220 KB Output is correct
22 Correct 821 ms 156796 KB Output is correct
23 Correct 824 ms 156808 KB Output is correct
24 Correct 794 ms 156812 KB Output is correct
25 Correct 817 ms 156764 KB Output is correct
26 Correct 829 ms 159244 KB Output is correct
27 Correct 789 ms 159244 KB Output is correct
28 Correct 850 ms 156768 KB Output is correct
29 Correct 796 ms 156772 KB Output is correct
30 Correct 799 ms 156792 KB Output is correct