Submission #130872

#	Time	Username	Problem	Language	Result	Execution time	Memory
130872		MAMBA	Wall (IOI14_wall)	C++14	100 / 100	767 ms	92360 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int) k; i++)
#define lid id<<1
#define rid lid|1

const int N = 2e6 + 10;

int n2;	

int segMin[N << 2];
int segMax[N << 2];

inline int smin(int &a, int b) { return b < a ? a = b : a; }
inline int smax(int &a, int b) { return a < b ? a = b : a; }

inline void applyMax(int id, int val) {
	smax(segMin[id] , val);
	smax(segMax[id] , val);
}

inline void applyMin(int id, int val) {
	smin(segMin[id] , val);
	smin(segMax[id] , val);
}

inline void shift(int id) {
	applyMin(lid , segMax[id]);
	applyMin(rid , segMax[id]);
	applyMax(lid , segMin[id]);
	applyMax(rid , segMin[id]);
	segMin[id] = 0;
	segMax[id] = 1e5;
}

void segApplyMin(int s, int t, int val , int l = 0 , int r = n2 , int id = 1) {
	if (l >= s && r <= t) {
		applyMin(id , val);
		return;
	}
	int mid = l + r >> 1;
	shift(id);
	if (s < mid) segApplyMin(s  ,t , val , l , mid , lid);
	if (t > mid) segApplyMin(s , t , val , mid , r , rid);
}

void segApplyMax(int s, int t, int val , int l = 0 , int r = n2 , int id = 1) {
	if (l >= s && r <= t) {
		applyMax(id , val);
		return;
	}
	int mid = l + r >> 1;
	shift(id);
	if (s < mid) segApplyMax(s  ,t , val , l , mid , lid);
	if (t > mid) segApplyMax(s , t , val , mid , r , rid);
}
int res[N];

void dfs(int l = 0, int r = n2, int id = 1) {
	if (l == r - 1) {
		res[l] = segMin[id];
	//	cout << l << ' '<< segMin[id] << ' '<< segMax[id] << endl;
		return;
	}
	int mid= l +r >> 1;
	shift(id);
	dfs(l , mid, lid);
	dfs(mid ,r, rid);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

	n2 = n;

	fill(segMax , segMax + (N << 2) , 1e5 + 1);

	rep(i , 0 , k) 
		op[i] == 1 ? 
			segApplyMax(left[i] , right[i] + 1 , height[i]) :
			segApplyMin(left[i] , right[i] + 1 , height[i]);
//	cout << "DONE" << endl;

	dfs();

	memcpy(finalHeight , res , 4 * n2);

	return;
}

Compilation message (stderr)

wall.cpp: In function 'void segApplyMin(int, int, int, int, int, int)':
wall.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wall.cpp: In function 'void segApplyMax(int, int, int, int, int, int)':
wall.cpp:55:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wall.cpp: In function 'void dfs(int, int, int)':
wall.cpp:68:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid= l +r >> 1;
           ~~^~

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