Submission #170337

#	Time	Username	Problem	Language	Result	Execution time	Memory
170337		ngmh	Wall (IOI14_wall)	C++11	100 / 100	1556 ms	224764 KiB

wall

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

struct node {
	int s, e, m, mini, maxi;
	node *l, *r;
	node(int _s, int _e){
		s = _s; e = _e; m = (s+e)/2; mini = 0; maxi = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void minimise(int v){
		maxi = min(v, max(mini, maxi));
		mini = min(mini, maxi);
	}
	void maximise(int v){
		mini = max(v, min(mini, maxi));
		maxi = max(mini, maxi);
	}
	void propogate(){
		if(s == e) return;
		l->maximise(mini);
		r->maximise(mini);
		l->minimise(maxi);
		r->minimise(maxi);
	}
	void backpropogate(){
		if(s == e) return;
		mini = min(l->mini, r->mini);
		maxi = max(l->maxi, r->maxi);
	}
	void add(int x, int y, int v){
		if(s == x && e == y){ maximise(v); return; }
		propogate();
		if(x > m) r->add(x, y, v);
		else if(y <= m) l->add(x, y, v);
		else l->add(x, m, v), r->add(m+1, y, v);
		backpropogate();
	}
	void remove(int x, int y, int v){
		if(s == x && e == y){ minimise(v); return; }
		propogate();
		if(x > m) r->remove(x, y, v);
		else if(y <= m) l->remove(x, y, v);
		else l->remove(x, m, v), r->remove(m+1, y, v);
		backpropogate();
	}
	int point_query(int x){
		if(s == e) return mini;
		propogate();
		if(x > m) return r->point_query(x);
		else if(x <= m) return l->point_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(int i = 0; i < k; i++){
		if(op[i] == 1) root->add(left[i], right[i], height[i]);
		else root->remove(left[i], right[i], height[i]);
	}
	for(int i = 0; i < n; i++) finalHeight[i] = root->point_query(i);
}

Compilation message (stderr)

wall.cpp: In member function 'int node::point_query(int)':
wall.cpp:56:2: warning: control reaches end of non-void function [-Wreturn-type]
  }
  ^

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