Submission #640215

#	Time	Username	Problem	Language	Result	Execution time	Memory
640215		ymm	Wall (IOI14_wall)	C++17	100 / 100	700 ms	60568 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

static const int N = 1<<21;
static int mn[N<<1];
static int mx[N<<1];

static inline void ppg(int i)
{
	if (mn[i] == mx[i]) {
		mn[2*i+1] = mx[2*i+1] = mn[i];
		mn[2*i+2] = mx[2*i+2] = mn[i];
	}
}

static inline void up(int i)
{
	mn[i] = min(mn[2*i+1], mn[2*i+2]);
	mx[i] = max(mx[2*i+1], mx[2*i+2]);
}

static void inc(int l, int r, int h, int i=0, int b=0, int e=N)
{
	if (l <= b && e <= r && mx[i] <= h) {
		mn[i] = mx[i] = h;
		return;
	}
	if (r <= b || e <= l || mn[i] >= h)
		return;
	ppg(i);
	inc(l, r, h, 2*i+1, b, (b+e)/2);
	inc(l, r, h, 2*i+2, (b+e)/2, e);
	up(i);
}

static void dec(int l, int r, int h, int i=0, int b=0, int e=N)
{
	if (l <= b && e <= r && mn[i] >= h) {
		mn[i] = mx[i] = h;
		return;
	}
	if (r <= b || e <= l || mx[i] <= h)
		return;
	ppg(i);
	dec(l, r, h, 2*i+1, b, (b+e)/2);
	dec(l, r, h, 2*i+2, (b+e)/2, e);
	up(i);
}

static int get(int p, int i=0, int b=0, int e=N)
{
	if (mn[i] == mx[i])
		return mn[i];
	if (p < (b+e)/2)
		return get(p, 2*i+1, b, (b+e)/2);
	else
		return get(p, 2*i+2, (b+e)/2, e);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	Loop (i,0,k) {
		if (op[i] == 1)
			inc(left[i], right[i]+1, height[i]);
		else
			dec(left[i], right[i]+1, height[i]);
	}
	Loop (i,0,n)
		finalHeight[i] = get(i);
}

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