Submission #969264

#	Time	Username	Problem	Language	Result	Execution time	Memory
969264		Hugo1729	Wall (IOI14_wall)	C++11	8 / 100	3059 ms	13396 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

const int MAXN=100000*4;
int sz=1;
int a[MAXN],b[MAXN];

void push(int v){
    a[2*v]=max(b[v*2],min(a[v],a[2*v]));
    a[2*v+1]=max(b[v*2+1],min(a[v],a[2*v+1]));

    b[2*v]=min(a[v*2],max(b[v],b[2*v]));
    b[2*v+1]=min(a[v*2+1],max(b[v],b[2*v+1]));
}

void update1(int v, int tl, int tr, int l, int r, int val){
    if(l>r)return;
    if(tl==l&&tr==r){
        b[v]=min(a[v],max(b[v],val));
    }else{
        push(v);
        int mid=(tl+tr)/2;
        update1(v*2,tl,mid,l,min(mid,r),val);
        update1(v*2+1,mid+1,tr,max(mid+1,l),r,val);
    }
}

void update2(int v, int tl, int tr, int l, int r, int val){
    if(l>r)return;
    if(tl==l&&tr==r){
        a[v]=max(b[v],min(a[v],val));
    }else{
        push(v);
        int mid=(tl+tr)/2;
        update2(v*2,tl,mid,l,min(mid,r),val);
        update2(v*2+1,mid+1,tr,max(mid+1,l),r,val);
    }
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    while(sz<n)sz<<=1;

    for(int i=1;i<2*sz;i++){
        a[i]=100001;
        b[i]=0;
    }

    for(int i=k-1;i>=0;i--){
        if(op[i]==1)update1(1,1,sz,left[i]+1,right[i]+1,height[i]);
        else update2(1,1,sz,left[i]+1,right[i]+1,height[i]);

        for(int i=1;i<sz;i++)push(i);
    }

    for(int i=0;i<n;i++)finalHeight[i]=b[i+sz];


    return;
}

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