oj.uz

Submission #130844

# Submission time Handle Problem Language Result Execution time Memory
130844 2019-07-16T07:07:38 Z MAMBA Wall (IOI14_wall) C++17
8 / 100
 3000 ms 21060 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]);
}

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

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.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 12 ms 632 KB Output is correct
4 Correct 108 ms 1272 KB Output is correct
5 Correct 112 ms 1144 KB Output is correct
6 Correct 114 ms 1272 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 219 ms 14368 KB Output is correct
3 Correct 1702 ms 8528 KB Output is correct
4 Execution timed out 3089 ms 20936 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
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 12 ms 632 KB Output is correct
4 Correct 108 ms 1272 KB Output is correct
5 Correct 113 ms 1272 KB Output is correct
6 Correct 113 ms 1272 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 220 ms 14200 KB Output is correct
9 Correct 1702 ms 8536 KB Output is correct
10 Execution timed out 3021 ms 21060 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 5 ms 764 KB Output is correct
3 Correct 12 ms 632 KB Output is correct
4 Correct 108 ms 1272 KB Output is correct
5 Correct 113 ms 1208 KB Output is correct
6 Correct 116 ms 1324 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 220 ms 14328 KB Output is correct
9 Correct 1714 ms 8576 KB Output is correct
10 Execution timed out 3023 ms 20932 KB Time limit exceeded
11 Halted 0 ms 0 KB -