oj.uz

Submission #774016

# Submission time Handle Problem Language Result Execution time Memory
774016 2023-07-05T11:03:21 Z danikoynov Wall (IOI14_wall) C++14
0 / 100
 153 ms 133360 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].max2)
    {
        tree[root].max1 = val;
        tree[root].max2 = -inf;
    }
    else
        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].min2)
    {
        tree[root].min1 = val;
        tree[root].min2 = inf;
    }
    else
        tree[root].min1 = max(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;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 125644 KB Output is correct
2 Correct 46 ms 125520 KB Output is correct
3 Incorrect 48 ms 125540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 125516 KB Output is correct
2 Correct 153 ms 133360 KB Output is correct
3 Incorrect 103 ms 128916 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 125500 KB Output is correct
2 Correct 47 ms 125560 KB Output is correct
3 Incorrect 56 ms 125516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 125512 KB Output is correct
2 Correct 49 ms 125568 KB Output is correct
3 Incorrect 48 ms 125516 KB Output isn't correct
4 Halted 0 ms 0 KB -