Submission #1131949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131949		anngela	Wall (IOI14_wall)	C++20	0 / 100	74 ms	8004 KiB

wall

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

#define fs (x << 1)
#define fd ((x << 1) | 1)
const int MAX_N = 2e6 + 1;
const int INF = 1e9;
int rez[MAX_N];

class SegTree {
public:
    SegTree(int n = 0): n{n}, t{4 * n}, U{4 * n}, D{4 * n} {}
    
    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(fs, U[x]);
            Add(fd, U[x]);
        }
        if (D[x] != INF)
        {
            Dec(fs, D[x]);
            Dec(fd, 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 || l > r)
            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(fs, l, m, a, b, h, type);
        Update(fd, 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)
        {
            rez[l] = t[x];
            return;
        }
        
        if (l != r) 
			PushDown(x);
        int m = (l + r) / 2;
        GetRez(fs, l, m);
        GetRez(fd, 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] = rez[i];
}

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