제출 #809081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
809081		ZeroCool	벽 (IOI14_wall)	C++14	100 / 100	515 ms	77360 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
 
const int mxn = 2000010;
const int inf = INT_MAX;
 
using namespace std;
 
struct Node{
	int mx = 0;
	int mn = 0;
};
 
int res[mxn];
Node seg[2 * (1<<21) + 20];
 
void push(int k){
	//Minimize na levoto dete
	seg[k * 2].mn = min(seg[k * 2].mn, seg[k].mn);
    seg[k * 2].mx = min(seg[k * 2].mx, seg[k].mn);
	//Maximize na levoto dete
    seg[k * 2].mn = max(seg[k * 2].mn, seg[k].mx);
    seg[k * 2].mx = max(seg[k * 2].mx, seg[k].mx);
	//Minimize na desnoto dete
    seg[k * 2 + 1].mn = min(seg[k * 2 + 1].mn, seg[k].mn);
    seg[k * 2 + 1].mx = min(seg[k * 2 + 1].mx, seg[k].mn);
	//Maximize na desnoto dete
    seg[k * 2 + 1].mn = max(seg[k * 2 + 1].mn, seg[k].mx);
    seg[k * 2 + 1].mx = max(seg[k * 2 + 1].mx, seg[k].mx);
}
 
void update(int k,int l,int r,int i,int j,int v,int t){
	if(l > j || r < i)return;
	if(i <= l && r<= j){
		if(t==1){
			//Maximize operacija
			seg[k].mn = max(seg[k].mn,v);
			seg[k].mx = max(seg[k].mx,v);
		}else{
			//Minimize operacija
			seg[k].mn = min(seg[k].mn,v);
			seg[k].mx = min(seg[k].mx,v);
		}
		return;
	}
	push(k);
	seg[k].mn = inf;
    seg[k].mx = 0;
	int mid = (l+r)/2;
	update(k*2,l,mid,i,j,v,t);
	update(k*2+1,mid+1,r,i,j,v,t);
}
 
void get(int k,int l,int r){
	if(l == r){
		res[l] = seg[k].mn;
		return;
	}
	push(k);
	int mid = (l+r)/2;
	get(k*2,l,mid);
	get(k*2+1,mid+1,r);
}
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = 0;i<k;i++){
		update(1,0,n-1,left[i],right[i],height[i],op[i]);
	}
	get(1,0,n-1);
	for(int i = 0;i<n;i++){
		finalHeight[i] = res[i];
	}
	
}

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