제출 #600320

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600320		NicolaAbusaad2014	벽 (IOI14_wall)	C++14	0 / 100	1 ms	212 KiB

wall

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

using namespace std;
vector<long>mx1,mx2,mn1,mn2;
void update_add(long l,long r,long nl,long nr,long node,long val)
{
    if(l>nr||r<nl||val<=mn1[node]){
        return;
    }
    if(val<mn2[node]){
        mn1[node]=val;
        return;
    }
    update_add(l,r,nl,(nl+nr)/2,node*2,val);
    update_add(l,r,((nl+nr)/2)+1,nr,(node*2)+1,val);
    mn1[node]=min(mn1[node*2],mn1[(node*2)+1]);
    mn2[node]=1e9;
    if(mn1[node*2]>mn1[node]){
        mn2[node]=min(mn2[node],mn1[node*2]);
    }
    if(mn1[(node*2)+1]>mn1[node]){
        mn2[node]=min(mn2[node],mn1[(node*2)+1]);
    }
    mn2[node]=min(mn2[node],mn2[node*2]);
    mn2[node]=min(mn2[node],mn2[(node*2)+1]);
}
void update_remove(long l,long r,long nl,long nr,long node,long val)
{
    if(l>nr||r<nl||val>=mx1[node]){
        return;
    }
    if(val>mx2[node]){
        mx1[node]=val;
        return;
    }
    update_remove(l,r,nl,(nl+nr)/2,node*2,val);
    update_remove(l,r,((nl+nr)/2)+1,nr,(node*2)+1,val);
    mx1[node]=max(mx1[node*2],mx1[(node*2)+1]);
    mx2[node]=-1e9;
    if(mx1[node*2]<mx1[node]){
        mx2[node]=max(mn2[node],mx1[node*2]);
    }
    if(mx1[(node*2)+1]>mx1[node]){
        mx2[node]=max(mx2[node],mx1[(node*2)+1]);
    }
    mx2[node]=min(mx2[node],mx2[node*2]);
    mx2[node]=min(mx2[node],mx2[(node*2)+1]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    long N=n;
    while(N&(N-1)){
        N=N&(N-1);
    }
    N*=2;
    mx1.resize(2*N);
    mx2.resize(2*N);
    mn1.resize(2*N);
    mn2.resize(2*N);
    for(int i=0;i<2*N;i++){
        mx1[i]=0;
        mx1[i]=-1e9;
        mn1[i]=0;
        mn2[i]=1e9;
    }
    for(int i=0;i<k;i++){
        if(op[i]==1){
            update_add(left[i],right[i],0,N-1,1,height[i]);
            continue;
        }
        update_remove(left[i],right[i],0,N-1,1,height[i]);
    }
    for(int i=0;i<n;i++){
        finalHeight[i]=mx1[N+i];
    }
    return;
}

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