oj.uz

Submission #838967

# Submission time Handle Problem Language Result Execution time Memory
838967 2023-08-28T11:14:20 Z midi Wall (IOI14_wall) C++14
8 / 100
 194 ms 14280 KB 
#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 10'010ll
#define sgN (1ll<<14ll)
#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 nloc, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	n = nloc;
	// finalHeight = new int[mxN];
	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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 3 ms 836 KB Output is correct
3 Correct 2 ms 976 KB Output is correct
4 Correct 7 ms 980 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 4 ms 980 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 179 ms 14280 KB Output is correct
3 Incorrect 158 ms 7904 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 8 ms 980 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 186 ms 13668 KB Output is correct
9 Incorrect 157 ms 7908 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 7 ms 1032 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 194 ms 13768 KB Output is correct
9 Incorrect 156 ms 7896 KB Output isn't correct
10 Halted 0 ms 0 KB -