oj.uz

Submission #130848

# Submission time Handle Problem Language Result Execution time Memory
130848 2019-07-16T07:17:34 Z MAMBA Wall (IOI14_wall) C++14
61 / 100
 3000 ms 63232 KB 
#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 , 17) {

		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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 42 ms 1144 KB Output is correct
5 Correct 50 ms 1112 KB Output is correct
6 Correct 49 ms 1148 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 632 KB Output is correct
2 Correct 221 ms 8728 KB Output is correct
3 Correct 567 ms 4680 KB Output is correct
4 Correct 1798 ms 12228 KB Output is correct
5 Correct 788 ms 12760 KB Output is correct
6 Correct 802 ms 12664 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 42 ms 1144 KB Output is correct
5 Correct 49 ms 1144 KB Output is correct
6 Correct 52 ms 1144 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 218 ms 8784 KB Output is correct
9 Correct 571 ms 4856 KB Output is correct
10 Correct 1786 ms 12128 KB Output is correct
11 Correct 786 ms 12896 KB Output is correct
12 Correct 780 ms 12664 KB Output is correct
13 Correct 3 ms 632 KB Output is correct
14 Correct 261 ms 9068 KB Output is correct
15 Correct 129 ms 2168 KB Output is correct
16 Correct 1827 ms 12580 KB Output is correct
17 Correct 864 ms 12664 KB Output is correct
18 Correct 854 ms 12536 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 42 ms 1144 KB Output is correct
5 Correct 49 ms 1144 KB Output is correct
6 Correct 49 ms 1144 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 218 ms 8768 KB Output is correct
9 Correct 568 ms 4760 KB Output is correct
10 Correct 1803 ms 12088 KB Output is correct
11 Correct 787 ms 12764 KB Output is correct
12 Correct 773 ms 12664 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 262 ms 8796 KB Output is correct
15 Correct 128 ms 2040 KB Output is correct
16 Correct 1860 ms 12536 KB Output is correct
17 Correct 856 ms 12560 KB Output is correct
18 Correct 862 ms 12456 KB Output is correct
19 Execution timed out 3053 ms 63232 KB Time limit exceeded
20 Halted 0 ms 0 KB -