제출 #676337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676337		alexdd	벽 (IOI14_wall)	C++17	0 / 100	144 ms	9628 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = LLONG_MAX;
struct node
{
    ll down_lim=0;
    ll up_lim=INF;
};
node aint[810001];
void propagate(int nod)
{
    aint[nod*2].up_lim = min(aint[nod*2].up_lim, aint[nod].up_lim);
    aint[nod*2].down_lim = min(aint[nod*2].down_lim, aint[nod*2].up_lim);

    aint[nod*2].down_lim = max(aint[nod*2].down_lim, aint[nod].down_lim);
    aint[nod*2].up_lim = max(aint[nod*2].up_lim, aint[nod*2].down_lim);

    aint[nod*2+1].up_lim = min(aint[nod*2+1].up_lim, aint[nod].up_lim);
    aint[nod*2+1].down_lim = min(aint[nod*2+1].down_lim, aint[nod*2+1].up_lim);

    aint[nod*2+1].down_lim = max(aint[nod*2+1].down_lim, aint[nod].down_lim);
    aint[nod*2+1].up_lim = max(aint[nod*2+1].up_lim, aint[nod*2+1].down_lim);

}
void upd2(ll nod, ll st, ll dr, ll le, ll ri, ll newh)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        aint[nod].up_lim = min(aint[nod].up_lim, newh);
        aint[nod].down_lim = min(aint[nod].down_lim, aint[nod].up_lim);
        return;
    }
    ll mij=(st+dr)/2;
    propagate(nod);
    upd2(nod*2,st,mij,le,min(mij,ri),newh);
    upd2(nod*2+1,mij+1,dr,max(mij+1,le),ri,newh);
}
void upd1(ll nod, ll st, ll dr, ll le, ll ri, ll newh)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        aint[nod].down_lim = max(aint[nod].down_lim, newh);
        aint[nod].up_lim = max(aint[nod].up_lim, aint[nod].down_lim);
        return;
    }
    ll mij=(st+dr)/2;
    propagate(nod);
    upd1(nod*2,st,mij,le,min(mij,ri),newh);
    upd1(nod*2+1,mij+1,dr,max(mij+1,le),ri,newh);
}
ll rez[200001];
void get_rez(ll nod, ll st, ll dr)
{
    if(st==dr)
    {
        if(aint[nod].up_lim == aint[nod].down_lim)
            rez[st]=aint[nod].up_lim;
        else
            rez[st]=aint[nod].down_lim;
        return;
    }
    propagate(nod);
    ll mij=(st+dr)/2;
    get_rez(nod*2,st,mij);
    get_rez(nod*2+1,mij+1,dr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i=0;i<n;i++)
        rez[i] = 0;
    for(int i=0;i<k;i++)
    {
        if(op[i]==1)
            upd1(1,0,n-1,left[i],right[i],height[i]);
        else
            upd2(1,0,n-1,left[i],right[i],height[i]);
    }

    get_rez(1,0,n-1);
    for(int i=0;i<n;i++)
        finalHeight[i]=rez[i];
    return;
}
/**


*/

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