제출 #566012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
566012		Jesus	벽 (IOI14_wall)	C++14	0 / 100	130 ms	262144 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>

using namespace std;

int lim;

struct operacion{
    int tipo=0;
    int h=0;
    int izq=0;
    int der=0;
};

queue<operacion> st[8000008];

void st_iniciar(int i=1,int j=lim,int pos=1){

}

void st_actualizar(int tp,int alt,int izq,int der,int i=0,int j=lim-1,int pos=1){
    if(izq==i&&der==j){
        operacion aux;
        aux.tipo=tp;
        aux.h=alt;
        aux.der=der;
        aux.izq=izq;
        st[pos].push(aux);
    }
    else{
        while(st[pos].size()>0){
            operacion aux=st[pos].front();
            operacion aux2=aux;
            aux2.der=(i+j)/2;
            st[pos*2].push(aux2);
            aux2.der=aux.der;
            aux2.izq=(i+j)/2+1;
            st[pos*2+1].push(aux2);
            st[pos].pop();
        }
        if(izq<=(i+j)/2){
            st_actualizar(tp,alt,max(izq,i),min(der,(i+j)/2),i,(i+j)/2,pos*2);
        }
        if(der>(i+j)/2){
            st_actualizar(tp,alt,max(izq,(i+j)/2+1),min(der,j),(i+j)/2+1,j,pos*2+1);
        }
    }
}

int resultado[2000000];

void revision(int i=0,int j=lim-1,int pos=1){
    if(i==j){
        while(st[pos].size()>0&&st[pos].front().tipo==2){
            st[pos].pop();
        }
        while(st[pos].size()>0){
            if(st[pos].front().tipo==1){
                resultado[i]=max(resultado[i],st[pos].front().h);
            }
            else{
                resultado[i]=min(resultado[i],st[pos].front().h);
            }
            st[pos].pop();
        }
    }
    else{
        while(st[pos].size()>0){
            operacion aux=st[pos].front();
            operacion aux2=aux;
            aux2.der=(i+j)/2;
            st[pos*2].push(aux2);
            aux2.der=aux.der;
            aux2.izq=(i+j)/2+1;
            st[pos*2+1].push(aux2);
            st[pos].pop();
        }
        revision(i,(i+j)/2,pos*2);
        revision((i+j)/2+1,j,pos*2+1);
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    lim=n;
    for(int i=0;i<k;i++){
        st_actualizar(op[i],height[i],left[i],right[i]);
    }
    revision();
    for(int i=0;i<n;i++){
        finalHeight[i]=resultado[i];
    }

  return;
}

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