Submission #676207

#	Time	Username	Problem	Language	Result	Execution time	Memory
676207		alexdd	벽 (IOI14_wall)	C++17	0 / 100	134 ms	8096 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1000000007;
struct node
{
    int down_lim=0;
    int up_lim=INF;
    int last = 0;
    bool isProp = 1;
};
node aint[810001];
void upd(int nod, int st, int dr, int le, int ri, int tip, int newh)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        if(tip==1)
        {
            aint[nod].last = tip;
            if(tip==1)
                aint[nod].down_lim = max(aint[nod].down_lim, newh);
            else
                aint[nod].up_lim = min(aint[nod].up_lim, newh);
        }
        return;
    }
    int mij=(st+dr)/2;
    upd(nod*2,st,mij,le,min(mij,ri),tip,newh);
    upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,tip,newh);
    aint[nod].last = -1;
}
int rez[200001];
void get_rez(int nod, int st, int dr, int sus, int jos, bool done, int lastval)
{
    if(!done && aint[nod].last != -1)
    {
        done = 1;
        if(aint[nod].last == 1)
            lastval = aint[nod].down_lim;
        else
            lastval = aint[nod].up_lim;
    }
    sus = min(sus, aint[nod].up_lim);
    jos = max(jos, aint[nod].down_lim);
    if(st==dr)
    {
        if(sus < jos)
        {
            rez[st] = lastval;
        }
        else
        {
            rez[st] = min(rez[st],sus);
            rez[st] = max(rez[st],jos);
        }
        return;
    }
    int mij=(st+dr)/2;
    get_rez(nod*2,st,mij,sus,jos,done,lastval);
    get_rez(nod*2,mij+1,dr,sus,jos,done,lastval);
}
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++)
    {
        upd(1,0,n-1,left[i],right[i],op[i],height[i]);
    }

    get_rez(1,0,n-1,INF,0,0,-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