Submission #881224

#	Time	Username	Problem	Language	Result	Execution time	Memory
881224		OAleksa	Wall (IOI14_wall)	C++14	100 / 100	700 ms	75956 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
//#define int long long
#define f first
#define s second
const int maxn = 2e6 + 69;
const int inf = 1e9 + 69;
int mn[4 * maxn], mx[4 * maxn], lst[4 * maxn];
void push(int v) {
	int ch1 = v * 2, ch2 = v * 2 + 1;
	int a = mx[v], b = mn[v];
	int c = mx[ch1], d = mn[ch1];
	int e = mx[ch2], f = mn[ch2];
	if (a == 0 && b == inf)
		return;
	if (a >= d)
		mx[ch1] = mn[ch1] = a;
	else if (b <= c)
		mn[ch1] = mx[ch1] = b;
	else {
		mx[ch1] = max(mx[ch1], a);
		mn[ch1] = min(mn[ch1], b);
	}
	if (a >= f)
		mx[ch2] = mn[ch2] = a;
	else if (b <= e)
		mn[ch2] = mx[ch2] = b;
	else {
		mx[ch2] = max(mx[ch2], a);
		mn[ch2] = min(mn[ch2], b);
	}
	mn[v] = inf;
	mx[v] = 0;
	lst[ch1] = lst[ch2] = lst[v];
}
void updmax(int v, int tl, int tr, int l, int r, int x) {
	if (tl > r || tr < l)
		return;
	else if (tl >= l && tr <= r) {
		if (x > mn[v])
			mn[v] = mx[v] = x;
		else {
			mx[v] = max(mx[v], x);
			mn[v] = min(mn[v], inf);
		}
		lst[v] = 1;
	}
	else {
		push(v);
		int mid = (tl + tr) / 2;
		updmax(v * 2, tl, mid, l, r, x);
		updmax(v * 2 + 1, mid + 1, tr, l, r, x);
	}
}
void updmin(int v, int tl, int tr, int l, int r, int x) {
	if (tl > r || tr < l)
		return;
	else if (tl >= l && tr <= r) {
		if (x < mx[v])
			mx[v] = mn[v] = x;
		else {
			mx[v] = max(mx[v], 0);
			mn[v] = min(mn[v], x);
		}
		lst[v] = 0;
	}
	else {
		push(v);
		int mid = (tl + tr) / 2;
		updmin(v * 2, tl, mid, l, r, x);
		updmin(v * 2 + 1, mid + 1, tr, l, r, x);
	}
}
int get(int v, int tl, int tr, int p) {
	if (tl == tr) {
		if (lst[v])
			return mx[v];
		return mn[v];
	}
	else {
		int mid = (tl + tr) / 2;
		push(v);
		if (p <= mid)
			return get(v * 2, tl, mid, p);
		else
			return get(v * 2 + 1, mid + 1, tr, p);
	}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  	for (int i = 0;i < k;i++) {
  		left[i]++;
  		right[i]++;
  		if (op[i] == 1)
  			updmax(1, 1, n, left[i], right[i], height[i]);
  		else
  			updmin(1, 1, n, left[i], right[i], height[i]);
	}
  	for (int i = 0;i < n;i++)
  		finalHeight[i] = get(1, 1, n, i + 1);
  	return;
}

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