oj.uz

Submission #130845

# Submission time Handle Problem Language Result Execution time Memory
130845 2019-07-16T07:15:01 Z MAMBA Wall (IOI14_wall) C++14
61 / 100
 3000 ms 73700 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 , 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

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 504 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 44 ms 1020 KB Output is correct
5 Correct 52 ms 1144 KB Output is correct
6 Correct 51 ms 1016 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Correct 224 ms 8404 KB Output is correct
3 Correct 596 ms 4516 KB Output is correct
4 Correct 1876 ms 12088 KB Output is correct
5 Correct 823 ms 22584 KB Output is correct
6 Correct 810 ms 20844 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 6 ms 636 KB Output is correct
4 Correct 44 ms 1144 KB Output is correct
5 Correct 51 ms 1060 KB Output is correct
6 Correct 51 ms 1016 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 225 ms 8440 KB Output is correct
9 Correct 592 ms 4728 KB Output is correct
10 Correct 1875 ms 11796 KB Output is correct
11 Correct 826 ms 22520 KB Output is correct
12 Correct 838 ms 20848 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 281 ms 14428 KB Output is correct
15 Correct 135 ms 2296 KB Output is correct
16 Correct 1898 ms 21644 KB Output is correct
17 Correct 884 ms 21096 KB Output is correct
18 Correct 883 ms 21112 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 44 ms 1016 KB Output is correct
5 Correct 51 ms 1016 KB Output is correct
6 Correct 51 ms 1016 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 221 ms 8440 KB Output is correct
9 Correct 592 ms 4552 KB Output is correct
10 Correct 1872 ms 11992 KB Output is correct
11 Correct 831 ms 22424 KB Output is correct
12 Correct 827 ms 20976 KB Output is correct
13 Correct 3 ms 632 KB Output is correct
14 Correct 269 ms 14300 KB Output is correct
15 Correct 136 ms 2296 KB Output is correct
16 Correct 1907 ms 21600 KB Output is correct
17 Correct 890 ms 21036 KB Output is correct
18 Correct 885 ms 21020 KB Output is correct
19 Execution timed out 3032 ms 73700 KB Time limit exceeded
20 Halted 0 ms 0 KB -