Submission #130844

#	Time	Username	Problem	Language	Result	Execution time	Memory
130844		MAMBA	Wall (IOI14_wall)	C++17	8 / 100	3089 ms	21060 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]);
}

void build(int l = 0, int r = n2, int id = 1) {
	if (l == r - 1) {
		segMin[id] = segMax[id] = l;
		return;
	}
	int mid = l + r >> 1;
	build(l , mid , id << 1);
	build(mid , r, id << 1 | 1);
	segMin[id] = mergeMin(id);
	segMax[id] = mergeMax(id);
}

int segGetMin(int s, int t, int l = 0, int r = n2, int id = 1) {
	if (l >= s && r <= t) return segMin[id];
	if (r <= s || l >= t) return -1;
	int mid = l + r >> 1;
	return mergeMin(segGetMin(s , t , l, mid , id <<1 ) , segGetMin(s , t , mid , r, id << 1 | 1));
}

int segGetMax(int s, int t, int l = 0, int r = n2, int id = 1) {
	if (l >= s && r <= t) return segMax[id];
	if (r <= s || l >= t) return -1;
	int mid = l + r >> 1;
	return mergeMax(segGetMax(s , t , l, mid , id <<1 ) , segGetMax(s , t , mid , r, id << 1 | 1));
}

void segDeactive(int p , int l = 0, int r = n2 , int id = 1) {
	if (l == r - 1) {
		segMin[id] = segMax[id] = -1;
		return;
	}
	int mid = l +r >> 1;
	if (p < mid) segDeactive(p , l , mid , id << 1);
	else segDeactive(p , mid , r , id <<1 | 1);
	segMin[id] = mergeMin(id);
	segMax[id] = mergeMax(id);
}


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 , 20) {

	//	cout << " ::: " << att << endl;
	//	memset(flag , 0 , sizeof(flag));
		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) {
				//	cout << i << " : " << endl;
					int id = segGetMin(left[i] , right[i] + 1);
					if (id == -1 || mid[id] > height[i]) break;
					flag[id] = true;
					segDeactive(id);
				}
			}
			else {
				while (true) {
				//	cout << " : "  << i << endl;
					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 build(int, int, int)':
wall.cpp:40:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wall.cpp: In function 'int segGetMin(int, int, int, int, int)':
wall.cpp:50:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wall.cpp: In function 'int segGetMax(int, int, int, int, int)':
wall.cpp:57:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wall.cpp: In function 'void segDeactive(int, int, int, int)':
wall.cpp:66:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l +r >> 1;
            ~~^~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:83:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid[i] = lo[i] + hi[i] >> 1;
             ~~~~~~^~~~~~~

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