Submission #257394

#	Time	Username	Problem	Language	Result	Execution time	Memory
257394		Berted	Wall (IOI14_wall)	C++14	100 / 100	1110 ms	102648 KiB

wall

#include "wall.h"
#include <algorithm>
#include <utility>
#include <iostream>
#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

const int SZ = (1 << 22) + 5;

pii lz[SZ];
pii seg[SZ];

inline void prop(int idx, int L, int R)
{
	if (L <= R)
	{
		if (seg[idx] != lz[idx])
		{
			seg[idx] = lz[idx];
			if (L < R)
			{
				lz[2 * idx].fst = max(lz[2 * idx].fst, lz[idx].fst);
				lz[2 * idx].snd = max(lz[2 * idx].snd, lz[idx].fst);
				lz[2 * idx].fst = min(lz[2 * idx].fst, lz[idx].snd);
				lz[2 * idx].snd = min(lz[2 * idx].snd, lz[idx].snd);
				lz[2 * idx + 1].fst = max(lz[2 * idx + 1].fst, lz[idx].fst);
				lz[2 * idx + 1].snd = max(lz[2 * idx + 1].snd, lz[idx].fst);
				lz[2 * idx + 1].fst = min(lz[2 * idx + 1].fst, lz[idx].snd);
				lz[2 * idx + 1].snd = min(lz[2 * idx + 1].snd, lz[idx].snd);
			}
		}
	}
}

inline void merge(pii& p, const pii &l, const pii &r)
{
	p = make_pair(min(l.fst, r.fst), max(l.snd, r.snd));
}

void upd(int idx, int L, int R, int l, int r, int t, int v)
{
	prop(idx, L, R);
	if (l <= r)
	{
		if (L == l && R == r)
		{
			if (t == 1)
			{
				lz[idx].fst = max(v, lz[idx].fst);
				lz[idx].snd = max(v, lz[idx].snd);
			}
			else
			{
				lz[idx].fst = min(v, lz[idx].fst);
				lz[idx].snd = min(v, lz[idx].snd);
			}
			prop(idx, L, R);
		}
		else
		{
			int M = L + R >> 1;
			upd(2 * idx, L, M, l, min(M, r), t, v);
			upd(2 * idx + 1, M + 1, R, max(M + 1, l), r, t, v);
			merge(seg[idx], seg[2 * idx], seg[2 * idx + 1]);
			lz[idx] = seg[idx];
		}
	}
	//cout << "UPD [" << L << ", " << R << "] " << seg[idx].fst << ", " << seg[idx].snd << ", T = " << t << ", V = " << v << "\n";
}

inline int qry(int idx, int L, int R, int x)
{
	prop(idx, L, R);
	if (L == x && R == x) {return seg[idx].fst;}
	else
	{
		int M = L + R >> 1;
		if (x <= M) {return qry(2 * idx, L, M, x);}
		else {return qry(2 * idx + 1, M + 1, R, x);}
	}
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0; i < k; i++)
	{
		upd(1, 0, n - 1, left[i], right[i], op[i], height[i]);	
	}
	for (int i = 0; i < n; i++)
	{
		finalHeight[i] = qry(1, 0, n - 1, i);
	}
	return;
}

Compilation message (stderr)

wall.cpp: In function 'void upd(int, int, int, int, int, int, int)':
wall.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int M = L + R >> 1;
            ~~^~~
wall.cpp: In function 'int qry(int, int, int, int)':
wall.cpp:80:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int M = L + R >> 1;
           ~~^~~

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