oj.uz

Submission #1007351

# Submission time Handle Problem Language Result Execution time Memory
1007351 2024-06-24T16:42:11 Z jer033 Wall (IOI14_wall) C++17
61 / 100
 623 ms 262144 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

class SegTree{
public:
    int left_index;
    int right_index;
    int lo_value;
    int hi_value;
    int lo_update;
    int hi_update;
    SegTree* left_child;
    SegTree* right_child;
    SegTree* parent;

    SegTree(int l, int r, SegTree* magulang)
    {
        parent = magulang;
        left_index = l;
        right_index = r;
        lo_value = 0;
        hi_value = 0;
        lo_update = -1;
        hi_update = 999999;
        if (l==r)
        {
            left_child = nullptr;
            right_child = nullptr;
        }
        else
        {
            int m = (l+r)/2;
            left_child = new SegTree(l, m, this);
            right_child = new SegTree(m+1, r, this);
        }
    }

    void push()
    {
        if (hi_value < lo_update)
        {
            lo_value = lo_update;
            hi_value = lo_update;
        }
        else if (lo_value > hi_update)
        {
            lo_value = hi_update;
            hi_value = hi_update;
        }
        else
        {
            lo_value = max(lo_value, lo_update);
            hi_value = min(hi_value, hi_update);
        }

        if (left_child!=nullptr)
        {
            if (left_child->hi_update < lo_update)
            {
                left_child->lo_update = lo_update;
                left_child->hi_update = lo_update;
            }
            else if (left_child->lo_update > hi_update)
            {
                left_child->lo_update = hi_update;
                left_child->hi_update = hi_update;
            }
            else
            {
                left_child->lo_update = max(left_child->lo_update, lo_update);
                left_child->hi_update = min(left_child->hi_update, hi_update);
            }

            if (right_child->hi_update < lo_update)
            {
                right_child->lo_update = lo_update;
                right_child->hi_update = lo_update;
            }
            else if (right_child->lo_update > hi_update)
            {
                right_child->lo_update = hi_update;
                right_child->hi_update = hi_update;
            }
            else
            {
                right_child->lo_update = max(right_child->lo_update, lo_update);
                right_child->hi_update = min(right_child->hi_update, hi_update);
            }
        }
        lo_update = -1;
        hi_update = 999999;
    }

    void pull()
    {
        if (left_child != nullptr)
        {
            lo_value = min(left_child->lo_value, right_child->lo_value);
            hi_value = max(left_child->hi_value, right_child->hi_value);
        }
    }

    void modify_self(int typ, int h)
    {
        if (typ==1)
        {
            lo_update = h;
            if (hi_update < h)
                hi_update = h;
        }
        else
        {
            hi_update = h;
            if (lo_update > h)
                lo_update = h;
        }
    }

    void builder(int typ, int l, int r, int h)
    {
        //cout << "nakarating sa " << left_index << right_index << l << r << '\n';
        push();
        int mid_index = (left_index+right_index)/2;
        if ((l==left_index) and (r==right_index))
        {
            //grab_new_info();
            modify_self(typ, h);
            //update_children();
            //grab_new_info();
            //cout << "range is " << l << r << '\n';
        }
        else
        {
            push();
            if (l<=mid_index)
                left_child->builder(typ, l, min(mid_index, r), h);
            if (r>=(mid_index+1))
                right_child->builder(typ, max(l, mid_index+1), r, h);
            pull();
        }
    }

    void answer(int finalHeight[])
    {
        push();
        if (left_index == right_index)
        {
            finalHeight[left_index] = lo_value;
        }
        else
        {
            left_child->answer(finalHeight);
            right_child->answer(finalHeight);
        }
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    SegTree* seg = new SegTree(0, n-1, nullptr);
    //cout << "nagawa\n";
    for (int oper = 0; oper<k; oper++)
    {
        int typ = op[oper];
        int l = left[oper];
        int r = right[oper];
        int h = height[oper];
        seg->builder(typ, l, r, h);
        //cout << "operation " << oper << " complete\n";
    }
    seg->answer(finalHeight);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 576 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1920 KB Output is correct
5 Correct 4 ms 1888 KB Output is correct
6 Correct 5 ms 1884 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 110 ms 13872 KB Output is correct
3 Correct 161 ms 9808 KB Output is correct
4 Correct 459 ms 30800 KB Output is correct
5 Correct 257 ms 31824 KB Output is correct
6 Correct 229 ms 30276 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 8 ms 1916 KB Output is correct
5 Correct 6 ms 1884 KB Output is correct
6 Correct 4 ms 1884 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 82 ms 13908 KB Output is correct
9 Correct 154 ms 9736 KB Output is correct
10 Correct 493 ms 30800 KB Output is correct
11 Correct 251 ms 31824 KB Output is correct
12 Correct 236 ms 30388 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 83 ms 13956 KB Output is correct
15 Correct 36 ms 3632 KB Output is correct
16 Correct 623 ms 31136 KB Output is correct
17 Correct 269 ms 30548 KB Output is correct
18 Correct 252 ms 30548 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 568 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1880 KB Output is correct
5 Correct 5 ms 1880 KB Output is correct
6 Correct 5 ms 1884 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 82 ms 13908 KB Output is correct
9 Correct 160 ms 9808 KB Output is correct
10 Correct 488 ms 30800 KB Output is correct
11 Correct 244 ms 31960 KB Output is correct
12 Correct 248 ms 30544 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 77 ms 13996 KB Output is correct
15 Correct 28 ms 3676 KB Output is correct
16 Correct 602 ms 31028 KB Output is correct
17 Correct 241 ms 30624 KB Output is correct
18 Correct 248 ms 30548 KB Output is correct
19 Runtime error 573 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -