Submission #1194212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194212		PlayVoltz	Wall (IOI14_wall)	C++20	100 / 100	706 ms	214308 KiB

wall

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

struct node{
	int s, e, m, val, mx, mn;
	node *l, *r;
	
	node(int S, int E){
		s=S, e=E, m=(s+e)/2;
		val=0;
		mx=INT_MIN/2, mn=INT_MAX/2;
		if (s!=e){
			l=new node(s, m);
			r=new node(m+1, e);
		}
	}
	void propagate(){
		val=max(min(val, mn), mx);
		if (s!=e){
			l->mn=min(l->mn, mn);
			l->mx=max(min(l->mx, mn), mx);
			r->mn=min(r->mn, mn);
			r->mx=max(min(r->mx, mn), mx);
		}
		mn=INT_MAX/2;
		mx=INT_MIN/2;
	}
	void upmin(int left, int right, int v){
		propagate();
		if (s==left&&e==right){
			mn=min(mn, v);
			mx=min(mx, v);
			return;
		}
		if (right<=m)l->upmin(left, right, v);
		else if (left>m)r->upmin(left, right, v);
		else l->upmin(left, m, v), r->upmin(m+1, right, v);
	}
	void upmax(int left, int right, int v){
		propagate();
		if (s==left&&e==right){
			mx=max(mx, v);
			return;
		}
		if (right<=m)l->upmax(left, right, v);
		else if (left>m)r->upmax(left, right, v);
		else l->upmax(left, m, v), r->upmax(m+1, right, v);
	}
	int query(int i){
		propagate();
		if (s==e)return val;
		if (i<=m)return l->query(i);
		return r->query(i);
	}
}*st;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	st = new node(0, n-1);
	for (int i=0; i<k; ++i){
		if (op[i]==1)st->upmax(left[i], right[i], height[i]);
		else st->upmin(left[i], right[i], height[i]);
	}
	for (int i=0; i<n; ++i)finalHeight[i]=st->query(i);
}

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