Submission #952212

#	Time	Username	Problem	Language	Result	Execution time	Memory
952212		SmuggingSpun	Wall (IOI14_wall)	C++14	100 / 100	463 ms	99412 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
const int lim = 2e6 + 5;
const int INF = 2e9;
pair<int, int>st[lim << 2];
void solve(int id, int l, int r, int cur, int* ans){
	maximize(cur, st[id].first);
	minimize(cur, st[id].second);
	if(l == r){
		ans[l] = cur;
	}
	else{
		int m = (l + r) >> 1;
		solve(id << 1, l, m, cur, ans);
		solve(id << 1 | 1, m + 1, r, cur, ans);
	}
}
void update(int id, int l, int r, int cur, int u, int v, bool is_maximize){
	if(l > v || r < u){
		return;
	}
	maximize(cur, st[id].first);
	minimize(cur, st[id].second);
	if(u <= l && v >= r){
		if(is_maximize){
			st[id].first = cur;
		}
		else{
			st[id].second = cur;
		}
		return;
	}
	int m = (l + r) >> 1;
	update(id << 1, l, m, cur, u, v, is_maximize);
	update(id << 1 | 1, m + 1, r, cur, u, v, is_maximize);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = n << 2; i > 0; i--){
		st[i] = make_pair(0, INF);
	}
	for(int i = k - 1; i > -1; i--){
		update(1, 0, n - 1, height[i], left[i], right[i], op[i] == 1);
	}
	solve(1, 0, n - 1, 0, finalHeight);
}

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