제출 #645964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645964		beaconmc	벽 (IOI14_wall)	C++14	100 / 100	596 ms	67268 KiB

wall

#include "wall.h"
#include <iostream>

typedef int ll;
using namespace std;


#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)



ll lazy[4194304][2];
ll N = 2097152;
ll ans[2097152];

void prop(ll pos, ll mini, ll maxi){
	if (maxi>= lazy[pos][0]){
		lazy[pos][0] = maxi;
		lazy[pos][1] = maxi;
	}else{
		lazy[pos][1] = max(maxi, lazy[pos][1]);
	}

	if (mini<= lazy[pos][1]){
		lazy[pos][0] = mini;
		lazy[pos][1] = mini;
	}else{
		lazy[pos][0] = min(mini, lazy[pos][0]);
	}
}

void update(ll a, ll b, ll op, ll val, ll k=1, ll x=0, ll y=N-1){
	if (b<x || a>y) return;
	if (a<=x && y<=b){
		if(op){
			if (val >= lazy[k][0]){
				lazy[k][0] = val;
				lazy[k][1] = val;
			}else{
				lazy[k][1] = max(lazy[k][1],val);
			}
		}else{
			if (val <= lazy[k][1]){
				lazy[k][0] = val;
				lazy[k][1] = val;
			}else{
				lazy[k][0] = min(lazy[k][0],val);
			}
		}
		return;
	}
    prop(k*2,lazy[k][0],lazy[k][1]);
    prop(k*2+1,lazy[k][0],lazy[k][1]);
    lazy[k][0] = 100001;
    lazy[k][1] = -1;
    ll d = (x+y)/2;
    update(a,b,op,val,2*k,x,d);
    update(a,b,op,val,2*k+1,d+1,y);
    return;

}

void propagate(){
	FOR(i,1,N){
		prop(i*2, lazy[i][0],lazy[i][1]);
        prop(i*2+1, lazy[i][0],lazy[i][1]);
	}
	FOR(i,N,2*N){


        ans[i-N] = (max(min(0,lazy[i][0]), lazy[i][1]));
	}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	FOR(i,0,4194304){
		lazy[i][0] = 100001;
		lazy[i][1] = -1;
	}
	FOR(i,0,k){
		if (op[i]==2) op[i] = 0;
		update(left[i], right[i], op[i], height[i]);
	}
	propagate();
	FOR(i,0,n){
		finalHeight[i] = ans[i];
	}
}

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