Submission #872589

#	Time	Username	Problem	Language	Result	Execution time	Memory
872589		dsyz	Wall (IOI14_wall)	C++17	100 / 100	811 ms	224780 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = int;
#define MAXN (1000005)

struct node {
	node *l, *r;
	ll s,e,m,opmax,opmin;
	node(ll _s,ll _e){
		s=_s,e=_e,m=(s+e)/2;
		opmax = opmin = 0;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void minimise(ll x,ll y,ll nval){
		value();
		if(s==x&&e==y) {
			if(opmax > nval) {
				opmax = nval;
				if(opmin > nval)opmin=nval;
			}
			return;
		}
		if(x>m)r->minimise(x,y,nval);
		else if(y<=m)l->minimise(x,y,nval);
		else l->minimise(x,m,nval),r->minimise(m+1,y,nval);
		opmax = max(l->opmax, r->opmax);
		opmin = min(l->opmin, r->opmin);
	}
	void maximise(ll x,ll y,ll nval){
		value();
		if(s==x&&e==y) {
			if(opmin < nval) {
				opmin = nval;
				if(opmax < nval)opmax=nval;
			}
			return;
		}
		if(x>m)r->maximise(x,y,nval);
		else if(y<=m)l->maximise(x,y,nval);
		else l->maximise(x,m,nval),r->maximise(m+1,y,nval);
		opmax = max(l->opmax, r->opmax);
		opmin = min(l->opmin, r->opmin);
	}
	void value() {
		if(s==e) return;
		if(opmin > l->opmin || opmin > r->opmin) {
			l->opmin=max(l->opmin, opmin);
			r->opmin=max(r->opmin, opmin);
			if(l->opmax < l->opmin) l->opmax = l->opmin;
			if(r->opmax < r->opmin) r->opmax = r->opmin;
		}
		if(opmax < l->opmax || opmax < r->opmax) {
			l->opmax=min(l->opmax, opmax);
			r->opmax=min(r->opmax, opmax);
			if(l->opmax < l->opmin) l->opmin = l->opmax;
			if(r->opmax < r->opmin) r->opmin = r->opmax;
		}
	}
	ll query(ll x){
		value();
		if(s==e) {
			assert(opmin==opmax);
			return opmin;
		}
		if(x>m)return r->query(x);
		else return l->query(x);
	}
} *root;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	root = new node(0,n - 1);
	for(ll i = 0;i < k;i++){
		if(op[i] == 1){
			root -> maximise(left[i],right[i],height[i]);
		}else if(op[i] == 2){
			root -> minimise(left[i],right[i],height[i]);
		}
	}
	for(ll i = 0;i < n;i++){
		finalHeight[i] = root -> query(i);
	}
	return;
}

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