oj.uz

Submission #1007354

# Submission time Handle Problem Language Result Execution time Memory
1007354 2024-06-24T16:51:24 Z jer033 Wall (IOI14_wall) C++17
100 / 100
 731 ms 224596 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(int l, int r)
    {
        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);
            right_child = new SegTree(m+1, r);
        }
    }

    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);
    //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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1372 KB Output is correct
5 Correct 5 ms 1372 KB Output is correct
6 Correct 4 ms 1372 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 79 ms 8108 KB Output is correct
3 Correct 151 ms 5460 KB Output is correct
4 Correct 447 ms 18104 KB Output is correct
5 Correct 243 ms 18564 KB Output is correct
6 Correct 226 ms 18636 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 484 KB Output is correct
4 Correct 6 ms 1372 KB Output is correct
5 Correct 4 ms 1372 KB Output is correct
6 Correct 4 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 82 ms 8240 KB Output is correct
9 Correct 142 ms 5460 KB Output is correct
10 Correct 464 ms 18164 KB Output is correct
11 Correct 255 ms 18516 KB Output is correct
12 Correct 211 ms 18600 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 81 ms 8244 KB Output is correct
15 Correct 28 ms 2644 KB Output is correct
16 Correct 527 ms 18424 KB Output is correct
17 Correct 251 ms 18264 KB Output is correct
18 Correct 238 ms 18324 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1492 KB Output is correct
5 Correct 4 ms 1372 KB Output is correct
6 Correct 6 ms 1460 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 83 ms 8232 KB Output is correct
9 Correct 143 ms 5460 KB Output is correct
10 Correct 456 ms 18172 KB Output is correct
11 Correct 201 ms 18516 KB Output is correct
12 Correct 208 ms 18512 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 75 ms 8160 KB Output is correct
15 Correct 34 ms 2652 KB Output is correct
16 Correct 540 ms 18260 KB Output is correct
17 Correct 248 ms 18260 KB Output is correct
18 Correct 238 ms 18264 KB Output is correct
19 Correct 689 ms 224592 KB Output is correct
20 Correct 643 ms 222092 KB Output is correct
21 Correct 711 ms 224480 KB Output is correct
22 Correct 688 ms 222036 KB Output is correct
23 Correct 671 ms 222176 KB Output is correct
24 Correct 716 ms 222032 KB Output is correct
25 Correct 680 ms 222032 KB Output is correct
26 Correct 653 ms 224592 KB Output is correct
27 Correct 704 ms 224596 KB Output is correct
28 Correct 659 ms 222108 KB Output is correct
29 Correct 731 ms 222176 KB Output is correct
30 Correct 660 ms 222176 KB Output is correct