oj.uz

Submission #612202

# Submission time Handle Problem Language Result Execution time Memory
612202 2022-07-29T11:32:08 Z nohaxjustsoflo Wall (IOI14_wall) C++17
100 / 100
 744 ms 100060 KB 
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mxN = 2 * 1e5;

struct node
{
    int min, max, add, destruct;
};

struct segmentTree
{
    int size;
    vector<node> val;

    void build(int n, int index, int Lx, int Rx)
    {
        if(Rx - Lx == 1)
        {
            if(Lx < n)
            {
                val[index] = {0, 0, -1, -1};
            }
            else
            {
                val[index] = {INT_MAX, -INT_MAX, -1, -1};
            }
        }
        else
        {
            int m = (Lx + Rx) / 2;
            build(n, index * 2 + 1, Lx, m);
            build(n, index * 2 + 2, m, Rx);
            val[index] = {0, 0, -1, -1};
        }
    }

    void build(int n)
    {
        size = 1;
        while(size < n) size <<= 1;
        val = vector<node>(size * 2);
        build(n, 0, 0, size);
    }

    void add(int index, int h)
    {
        val[index].min = max(val[index].add, h);
        val[index].add = val[index].min;
        val[index].max = max(val[index].max, val[index].min);
        if(val[index].destruct != -1)
        {
            val[index].destruct = max(val[index].destruct, val[index].add);
        }
    }

    void destruct(int index, int h)
    {
        if(val[index].destruct != -1)
        {
            val[index].max = min(val[index].destruct, h);
        }
        else
        {
            val[index].max = h;
        }
        val[index].destruct = val[index].max;
        val[index].min =  min(val[index].min, val[index].max);
        if(val[index].add != -1)
        {
            val[index].add = min(val[index].add, val[index].destruct);
        }
    }

    node func(node left, node right)
    {
        return {min(left.min, right.min), max(left.max, right.max), -1, -1};
    }

    void add(int l, int r, int h, int index, int Lx, int Rx)
    {
        if(Rx <= l || Lx >= r) return;
        if(Lx >= l && Rx <= r)
        {
            add(index, h);
            return;
        }
        if(val[index].add != -1)
        {
            add(index * 2 + 1, val[index].add);
            add(index * 2 + 2, val[index].add);
            val[index].add = -1;
        }
        if(val[index].destruct != -1)
        {
            destruct(index * 2 + 1, val[index].destruct);
            destruct(index * 2 + 2, val[index].destruct);
            val[index].destruct = -1;
        }
        int m = (Rx + Lx) / 2;
        add(l, r, h, index * 2 + 1, Lx, m);
        add(l, r, h, index * 2 + 2, m, Rx);
        val[index] = func(val[index * 2 + 1], val[index * 2 + 2]);
    }

    void add(int l, int r, int h)
    {
        add(l, r, h, 0, 0, size);
    }

    void destruct(int l, int r, int h, int index, int Lx, int Rx)
    {
        if(Rx <= l || Lx >= r) return;
        if(Lx >= l && Rx <= r)
        {
            destruct(index, h);
            return;
        }
        if(val[index].destruct != -1)
        {
            destruct(index * 2 + 1, val[index].destruct);
            destruct(index * 2 + 2, val[index].destruct);
            val[index].destruct = -1;
        }
        if(val[index].add != -1)
        {
            add(index * 2 + 1, val[index].add);
            add(index * 2 + 2, val[index].add);
            val[index].add = -1;
        }
        int m = (Rx + Lx) / 2;
        destruct(l, r, h, index * 2 + 1, Lx, m);
        destruct(l, r, h, index * 2 + 2, m, Rx);
        val[index] = func(val[index * 2 + 1], val[index * 2 + 2]);
    }

    void destruct(int l, int r, int h)
    {
        destruct(l, r, h, 0, 0, size);
    }
    vector<int> ans;
    void print(int n, int index, int Lx, int Rx)
    {
        if(Rx - Lx == 1)
        {
            if(Lx < n)
            {
                ans.push_back(val[index].min);
            }
            return;
        }

        if(val[index].add != -1)
        {
            add(index * 2 + 1, val[index].add);
            add(index * 2 + 2, val[index].add);
            val[index].add = -1;
        }
        if(val[index].destruct != -1)
        {
            destruct(index * 2 + 1, val[index].destruct);
            destruct(index * 2 + 2, val[index].destruct);
            val[index].destruct = -1;
        }
        if(val[index].min == val[index].max && val[index].min != -1)
        {
            for(int i = 0; i < Rx - Lx; i++)
            {
                if(Lx + i < n)
                {
                    ans.push_back(val[index].min);
                }
                else
                {
                    break;
                }
            }
            return;
        }
        int m = (Rx + Lx) / 2;
        print(n, index * 2 + 1, Lx, m);
        print(n, index * 2 + 2, m, Rx);
    }

    void print(int n)
    {
        print(n, 0, 0, size);
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    segmentTree st;
    st.build(n);
    for(int i=0; i<k; i++)
    {
        int o=op[i], l=left[i], r=right[i], h=height[i];
        r++;
        if(o == 1)
        {
            st.add(l, r, h);
        }
        else
        {
            st.destruct(l, r, h);
        }
    }
    st.print(n);
    for(int i=0; i<n; i++) finalHeight[i]=st.ans[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1080 KB Output is correct
5 Correct 5 ms 1108 KB Output is correct
6 Correct 5 ms 1012 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 132 ms 13860 KB Output is correct
3 Correct 192 ms 8544 KB Output is correct
4 Correct 576 ms 22856 KB Output is correct
5 Correct 302 ms 23364 KB Output is correct
6 Correct 328 ms 21712 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 1108 KB Output is correct
5 Correct 7 ms 1108 KB Output is correct
6 Correct 6 ms 1004 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 139 ms 13896 KB Output is correct
9 Correct 187 ms 8652 KB Output is correct
10 Correct 559 ms 22732 KB Output is correct
11 Correct 297 ms 23216 KB Output is correct
12 Correct 300 ms 21716 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 141 ms 13912 KB Output is correct
15 Correct 45 ms 2592 KB Output is correct
16 Correct 668 ms 22788 KB Output is correct
17 Correct 298 ms 22152 KB Output is correct
18 Correct 313 ms 22152 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 432 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct
5 Correct 5 ms 1108 KB Output is correct
6 Correct 5 ms 1136 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 136 ms 13840 KB Output is correct
9 Correct 202 ms 8544 KB Output is correct
10 Correct 584 ms 22864 KB Output is correct
11 Correct 290 ms 23276 KB Output is correct
12 Correct 314 ms 21720 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 141 ms 13856 KB Output is correct
15 Correct 38 ms 2508 KB Output is correct
16 Correct 722 ms 22732 KB Output is correct
17 Correct 322 ms 22116 KB Output is correct
18 Correct 302 ms 22084 KB Output is correct
19 Correct 731 ms 99944 KB Output is correct
20 Correct 744 ms 100028 KB Output is correct
21 Correct 701 ms 99948 KB Output is correct
22 Correct 744 ms 99948 KB Output is correct
23 Correct 692 ms 99948 KB Output is correct
24 Correct 694 ms 100060 KB Output is correct
25 Correct 704 ms 100000 KB Output is correct
26 Correct 676 ms 99960 KB Output is correct
27 Correct 703 ms 99948 KB Output is correct
28 Correct 712 ms 99948 KB Output is correct
29 Correct 680 ms 99948 KB Output is correct
30 Correct 691 ms 100016 KB Output is correct