Submission #292821

#	Time	Username	Problem	Language	Result	Execution time	Memory
292821		oolimry	Wall (IOI14_wall)	C++14	100 / 100	1061 ms	232664 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef long long lint;
typedef pair<int,int> ii;

const int inf = 1023456789;

vector<int> ans;

struct node{
	int s, e, m;
	int low, high;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if(s != e){
			low = 0, high = inf;
			l = new node(s, m);
			r = new node(m+1, e);
		}
		else low = 0, high = 0;
	}
	
	void apply(int L, int H){
		if(L > high) low = high = L;
		else if(H < low) low = high = H;
		else{
			low = max(low, L);
			high = min(high, H);
		}
	}
	
	void push(){
		if(s == e) return;
		l->apply(low, high);
		r->apply(low, high);
		low = 0, high = inf;
	}
		
	void update(int S, int E, int op, int H){
		push();
		if(S == s && E == e){
			if(op == 1) apply(H, inf);
			else if(op == 2) apply(-inf, H);
			return;
		}
		else if(E <= m) l->update(S, E, op, H);
		else if(S >= m+1) r->update(S, E, op, H);
		else{
			l->update(S, m, op, H);
			r->update(m+1, E, op, H);
		}
	}
	
	void out(){
		push();
		//cout << s << " " << e << ": " << "(" << low << ", " << high << ")\n";
		if(s == e){
			ans.push_back(low);
			return;
		}
		else{
			l->out();
			r->out();
		}
	}
} *root;

void buildWall(int n, int Q, int op[], int L[], int R[], int H[], int finalHeight[]){
	root = new node(0, n-1);
	for(int q = 0;q < Q;q++){
		root->update(L[q], R[q], op[q], H[q]);
	}
	root->out();
	for(int i = 0;i < n;i++) finalHeight[i] = ans[i];
}

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