Submission #130845

#	Time	Username	Problem	Language	Result	Execution time	Memory
130845		MAMBA	Wall (IOI14_wall)	C++14	61 / 100	3032 ms	73700 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++)

const int N = 2e6 + 10;

int n2, lo[N], hi[N], mid[N];
bitset<N> flag;

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

inline int mergeMin(int a , int b) {
	if (a == -1) return b;
	if (b == -1) return a;
	return mid[a] < mid[b] ? a : b;
}

inline int mergeMax(int a, int b) {
	if (a == -1) return b;
	if (b == -1) return a;
	return mid[a] < mid[b] ? b : a;
}

inline int mergeMin(int id) {
	return mergeMin(segMin[id << 1] , segMin[id << 1| 1]);
}

inline int mergeMax(int id) {
	return mergeMax(segMax[id <<1 ] , segMax[id << 1 | 1]);
}

inline void build() {
	rep(i , 0 , n2)
		segMin[i + n2] = segMax[i + n2] = i;
	for (int i = n2 - 1; i; i--) {
		segMin[i] = mergeMin(i);
		segMax[i] = mergeMax(i);
	}
}

inline void segDeactive(int p) {
	p += n2;
	segMin[p] = segMax[p] = -1;
	while (p > 1) {
		p >>= 1;
		segMin[p] = mergeMin(p);
		segMax[p] = mergeMax(p);
	}
}

inline int segGetMin(int l , int r) {
	int best = -1;
	for (l += n2, r += n2; l < r; l >>= 1, r >>= 1) {
		if (l & 1) best = mergeMin(best , segMin[l++]);
		if (r & 1) best = mergeMin(best , segMin[--r]);
	}
	return best;
}

inline int segGetMax(int l , int r) {
	int best = -1;
	for (l += n2, r += n2; l < r; l >>= 1, r >>= 1) {
		if (l & 1) best = mergeMax(best , segMax[l++]);
		if (r & 1) best = mergeMax(best , segMax[--r]);
	}
	return best;
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	fill(hi , hi + n, 1e5 + 10);
	n2 = n;
	rep(att , 0 , 18) {

		flag.reset();
		rep(i , 0 , n) 
			mid[i] = lo[i] + hi[i] >> 1;
		build();
		for (int i = k - 1; ~i; i--) {
			if (op[i] == 1) {
				while (true) {
					int id = segGetMin(left[i] , right[i] + 1);
					if (id == -1 || mid[id] > height[i]) break;
					flag[id] = true;
					segDeactive(id);
				}
			}
			else {
				while (true) {
					int id = segGetMax(left[i] , right[i] + 1);
					if (id == -1 || mid[id] <= height[i]) break;
					segDeactive(id);
				}
			}
		}
		rep(i , 0 , n) {
			if (flag[i] || !mid[i]) 
				lo[i] = mid[i];
			else 
				hi[i] = mid[i];
		}
	}
	rep(i , 0 , n) finalHeight[i] = lo[i];
	return;
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:80:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid[i] = lo[i] + hi[i] >> 1;
             ~~~~~~^~~~~~~

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