Submission #427390

#	Time	Username	Problem	Language	Result	Execution time	Memory
427390		frodakcin	Wall (IOI14_wall)	C++17	61 / 100	738 ms	26868 KiB

wall

#include "wall.h"
#include <cassert>

bool ckmin(auto& a, const auto& b) {return b<a?a=b,1:0;}
bool ckmax(auto& a, const auto& b) {return b>a?a=b,1:0;}

const int MX = 1 << 21; // ~4m
const int INF = 0x3f3f3f3f;

int flr[MX], cel[MX];

void updf(int n, int v) {ckmax(flr[n], v); ckmax(cel[n], v);}
void updc(int n, int v) {ckmin(flr[n], v); ckmin(cel[n], v);}
void down(int n)
{
	updf(n<<1, flr[n]);
	updf(n<<1|1, flr[n]);
	updc(n<<1, cel[n]);
	updc(n<<1|1, cel[n]);
	flr[n]=-INF;
	cel[n]=INF;
}

void updf(int n, int l, int r, int ql, int qr, int v)
{
	if(ql <= l&&r <= qr) updf(n, v);
	else
	{
		int m=l+(r-l)/2;
		down(n);
		if(ql<m) updf(n<<1, l, m, ql, qr, v);
		if(m<qr) updf(n<<1|1, m, r, ql, qr, v);
	}
}

void updc(int n, int l, int r, int ql, int qr, int v)
{
	if(ql <= l&&r <= qr) updc(n, v);
	else
	{
		int m=l+(r-l)/2;
		down(n);
		if(ql<m) updc(n<<1, l, m, ql, qr, v);
		if(m<qr) updc(n<<1|1, m, r, ql, qr, v);
	}
}

void fill(int n, int l, int r, int *f)
{
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		down(n);
		fill(n<<1, l, m, f);
		fill(n<<1|1, m, r, f);
	}
	else
	{
		f[l]=flr[n];
		assert(flr[n]==cel[n]);
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for(int i=0;i<k;++i)
	{
		if(op[i]==1) updf(1, 0, n, left[i], right[i]+1, height[i]);
		if(op[i]==2) updc(1, 0, n, left[i], right[i]+1, height[i]);
	}
	fill(1, 0, n, finalHeight);
}

Compilation message (stderr)

wall.cpp:4:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    4 | bool ckmin(auto& a, const auto& b) {return b<a?a=b,1:0;}
      |            ^~~~
wall.cpp:4:27: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    4 | bool ckmin(auto& a, const auto& b) {return b<a?a=b,1:0;}
      |                           ^~~~
wall.cpp:5:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    5 | bool ckmax(auto& a, const auto& b) {return b>a?a=b,1:0;}
      |            ^~~~
wall.cpp:5:27: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    5 | bool ckmax(auto& a, const auto& b) {return b>a?a=b,1:0;}
      |                           ^~~~

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