Submission #282486

#	Time	Username	Problem	Language	Result	Execution time	Memory
282486		Kastanda	벽 (IOI14_wall)	C++11	100 / 100	844 ms	59888 KiB

wall

// M
#include<bits/stdc++.h>
#include "wall.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 2000006, MXS = N * 4, MXH = 1e5 + 3;
int n, MN[MXS], MX[MXS];
int * RS;
inline void Apply(int id, int mn, int mx)
{
        assert(mn >= mx);
        // mn :
        MN[id] = min(MN[id], mn);
        if (MX[id] > MN[id]) MX[id] = mn;
        // mx :
        MX[id] = max(MX[id], mx);
        if (MN[id] < MX[id]) MN[id] = mx;
}
inline void Shift(int id)
{
        Apply(lc, MN[id], MX[id]);
        Apply(rc, MN[id], MX[id]);
        MN[id] = MXH;
        MX[id] = 0;
}
void Add(int le, int ri, int mn, int mx, int id = 1, int l = 0, int r = n)
{
        if (ri <= l || r <= le)
                return ;
        if (le <= l && r <= ri)
                return void(Apply(id, mn, mx));
        Shift(id);
        Add(le, ri, mn, mx, lc, l, md);
        Add(le, ri, mn, mx, rc, md, r);
}
void DFS(int id = 1, int l = 0, int r = n)
{
        if (r - l < 2)
                return void(RS[l] = MX[id]);
        Shift(id);
        DFS(lc, l, md);
        DFS(rc, md, r);
}
void buildWall(int _n, int q, int * op, int * le, int * ri, int * A, int * Rs)
{
        n = _n; RS = Rs;
        for (int i = 0; i < q; i ++)
        {
                if (op[i] == 1)
                        Add(le[i], ri[i] + 1, MXH, A[i]);
                else
                        Add(le[i], ri[i] + 1, A[i], 0);
        }
        DFS();
}

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