oj.uz

Submission #838968

# Submission time Handle Problem Language Result Execution time Memory
838968 2023-08-28T11:15:14 Z midi Wall (IOI14_wall) C++14
100 / 100
 723 ms 102280 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 2'000'010ll
#define sgN (1ll<<21ll)
#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 41 ms 65876 KB Output is correct
2 Correct 44 ms 66040 KB Output is correct
3 Correct 43 ms 65960 KB Output is correct
4 Correct 48 ms 66072 KB Output is correct
5 Correct 44 ms 66080 KB Output is correct
6 Correct 46 ms 66092 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 65832 KB Output is correct
2 Correct 256 ms 73712 KB Output is correct
3 Correct 224 ms 69224 KB Output is correct
4 Correct 563 ms 83924 KB Output is correct
5 Correct 305 ms 79992 KB Output is correct
6 Correct 298 ms 80020 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 65872 KB Output is correct
2 Correct 43 ms 66040 KB Output is correct
3 Correct 43 ms 65988 KB Output is correct
4 Correct 47 ms 66176 KB Output is correct
5 Correct 53 ms 66140 KB Output is correct
6 Correct 47 ms 66104 KB Output is correct
7 Correct 41 ms 65868 KB Output is correct
8 Correct 269 ms 73728 KB Output is correct
9 Correct 226 ms 69256 KB Output is correct
10 Correct 576 ms 79484 KB Output is correct
11 Correct 311 ms 80076 KB Output is correct
12 Correct 298 ms 80008 KB Output is correct
13 Correct 41 ms 65876 KB Output is correct
14 Correct 266 ms 78872 KB Output is correct
15 Correct 80 ms 67144 KB Output is correct
16 Correct 723 ms 79664 KB Output is correct
17 Correct 313 ms 79692 KB Output is correct
18 Correct 328 ms 79720 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 65960 KB Output is correct
2 Correct 42 ms 66028 KB Output is correct
3 Correct 42 ms 66004 KB Output is correct
4 Correct 48 ms 66072 KB Output is correct
5 Correct 49 ms 66088 KB Output is correct
6 Correct 46 ms 66080 KB Output is correct
7 Correct 42 ms 65960 KB Output is correct
8 Correct 255 ms 73792 KB Output is correct
9 Correct 235 ms 69284 KB Output is correct
10 Correct 564 ms 79484 KB Output is correct
11 Correct 316 ms 80064 KB Output is correct
12 Correct 298 ms 79908 KB Output is correct
13 Correct 41 ms 65956 KB Output is correct
14 Correct 268 ms 78980 KB Output is correct
15 Correct 78 ms 67068 KB Output is correct
16 Correct 699 ms 79736 KB Output is correct
17 Correct 331 ms 79708 KB Output is correct
18 Correct 314 ms 79736 KB Output is correct
19 Correct 621 ms 97080 KB Output is correct
20 Correct 608 ms 99788 KB Output is correct
21 Correct 616 ms 102244 KB Output is correct
22 Correct 601 ms 99836 KB Output is correct
23 Correct 619 ms 99840 KB Output is correct
24 Correct 641 ms 99916 KB Output is correct
25 Correct 596 ms 99768 KB Output is correct
26 Correct 653 ms 102232 KB Output is correct
27 Correct 603 ms 102280 KB Output is correct
28 Correct 604 ms 99732 KB Output is correct
29 Correct 602 ms 99844 KB Output is correct
30 Correct 616 ms 99716 KB Output is correct