제출 #1131929

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131929		anngela	벽 (IOI14_wall)	C++20	0 / 100	70 ms	8008 KiB

wall

#include <vector>
#include <algorithm>
using namespace std;

#define ls (x << 1)
#define rs ((x << 1) | 1)

const int MAX_N = 2e6+7;
const int INF = 2e9;
int res[MAX_N];

class SegTree {
public:   
    SegTree(int n = 0): n{n}, t{4 * n, -INF}, U{4 * n, -INF}, D{4 * n, INF} {}
    
    void Dec(int x, int h)
    {
        t[x] = min(t[x], h);
        U[x] = min(U[x], h);
        D[x] = min(D[x], h);
    }
    
    void Add(int x, int h)
    {
        t[x] = max(t[x], h);
        U[x] = max(U[x], h);
        D[x] = max(D[x], h);
    }
    
    void PushDown(int x)
    {
        if (U[x] != -INF)
        {
            Add(ls, U[x]);
            Add(rs, U[x]);
        }
        if (D[x] != INF)
        {
            Dec(ls, D[x]);
            Dec(rs, D[x]);
        }
        U[x] = -INF, D[x] = INF;
    }
    
    void Update(int x, int l, int r, int a, int b, int h, int type)
    {
        if (l > b || r < a)
            return;
        
        if (a <= l && r <= b)
        {
            if (type == 1)
				Add(x, h);
            else 
				Dec(x, h);
            return;
        }
        
        if (l != r) 
			PushDown(x);
        int m = (l + r) / 2;
        Update(ls, l, m, a, b, h, type);
        Update(rs, m + 1, r, a, b, h, type);
    }
    
    void Update(int a, int b, int h, int type)
    {
		Update(1, 0, n - 1, a, b, h, type);
	}
	
    void GetRez(int x, int l, int r)
    {
        if (l == r)
        {
            res[l] = t[x];
            return;
        }
        
        if (l != r) 
			PushDown(x);
        int m = (l + r) / 2;
        GetRez(ls, l, m);
        GetRez(rs, m + 1, r);
    }
    
    void GetRez() { GetRez(1, 0, n - 1); }
private:    
    int n;
    vector<int> t;
    vector<int> U, D; // astea doua sunt lazy-uri pt "t"
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    SegTree t(n);
    for (int i = 0; i < k; ++i)
        t.Update(left[i], right[i], height[i], op[i]);
    
    t.GetRez();
    for (int i = 0; i < n; ++i)
		finalHeight[i] = res[i];
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39