Submission #838956

#	Time	Username	Problem	Language	Result	Execution time	Memory
838956		midi	Wall (IOI14_wall)	C++14	0 / 100	1 ms	368 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vc vector
typedef vc<ll> vcll;
#define pr pair
typedef pr<ll, ll> prll;

#define f0r(i,a,n) for (i=a; i<n; i++)
#define f1r(i,a,n) for (i=a; i<=n; i++)
#define r0f(i,n,a) for (i=n; i>a; i--)
#define r1f(i,n,a) for (i=n; i>=a; i--)

#define mxN 1'010ll
#define sgN (1ll<<11ll)
#define INF LLONG_MAX

ll n;

inline void amax(ll &a, ll b) { if (b>a) a=b; }
inline void amin(ll &a, ll b) { if (b<a) a=b; }

inline void camax(ll &a, ll b) { if (b>a) a=b; }
inline void camin(ll &a, ll b) { if (b<a) a=b; }

struct ST
{
	struct nd
	{
		ll down, up; // both lazy

		inline nd() { down=0; up=INF; } // -1 means "no lazy", "down" is incl., "up" is excl.
	};

	vc<nd> st;

	inline ST() { st.resize(sgN<<1); }

	inline void doprop(ll i, bool leaf)
	{
		if (leaf) return;

		ll newd=st[i].down; ll newu=st[i].up;
		st[i].down=0; st[i].up=INF;

		ll i2 = i<<1;

		amax(st[i2].down, newd);
		amax(st[i2].up, newd);
		amin(st[i2].down, newu);
		amin(st[i2].up, newu);

		i2++;

		amax(st[i2].down, newd);
		amax(st[i2].up, newd);
		amin(st[i2].down, newu);
		amin(st[i2].up, newu);

	}

	inline void dopropupd(ll i, ll newd, ll newu)
	{
		amax(st[i].down, newd);
		amax(st[i].up, newd);
		amin(st[i].down, newu);
		amin(st[i].up, newu);
	}

	void upd(ll i, ll lt, ll rt, ll l, ll r, ll h, bool id)
	{
		// printf("prop: \n");
		doprop(i, (lt+1==rt));
		// printf("yes\n");
		if (r<=lt || rt<=l) return;
		if (l<=lt && rt<=r)
		{
			// printf("i upd: %lli\n", i);
			if (id)
			{
				// printf("doing: \n");
				dopropupd(i, h, INF);
			}
			else
			{
				dopropupd(i, 0, h);
			}
			return;
		}

		ll nt=i<<1;
		ll mt= (lt+rt)>>1;

		upd(nt, lt, mt, l, r, h, id);
		upd(nt+1, mt, rt, l, r, h, id);
	}
	
	inline void upd(ll l, ll r, ll h, bool id) { upd(1, 0, sgN, l, r+1, h, id); }

	void doout(ll i, ll lt, ll rt, int out[])
	{
		doprop(i, (lt+1==rt));
		if (lt+1==rt)
		{
			if (lt<n) out[lt]=st[i].down;
			return;
		}

		ll nt = i<<1;
		ll mt = (lt+rt)>>1;

		doout(nt, lt, mt, out);
		doout(nt+1, mt, rt, out);
	}

	inline void doout(int out[]) { doout(1, 0, sgN, out); }
} st;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	ll i;
	f0r(i,0,k)
	{
		// printf("left[i]: %i, right[i]: %i, height[i]: %i, op[i]: %i\n", left[i], right[i], height[i], !(op[i]-1));
		st.upd(left[i], right[i], height[i], !(op[i]-1));
		// st.doout(finalHeight); // +1? // weird runtime error !!!!!
	}

	st.doout(finalHeight); // +1? // weird runtime error !!!!!
}

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