oj.uz

Submission #130872

# Submission time Handle Problem Language Result Execution time Memory
130872 2019-07-16T07:53:46 Z MAMBA Wall (IOI14_wall) C++14
100 / 100
 767 ms 92360 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int) k; i++)
#define lid id<<1
#define rid lid|1

const int N = 2e6 + 10;

int n2;	

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

inline int smin(int &a, int b) { return b < a ? a = b : a; }
inline int smax(int &a, int b) { return a < b ? a = b : a; }

inline void applyMax(int id, int val) {
	smax(segMin[id] , val);
	smax(segMax[id] , val);
}

inline void applyMin(int id, int val) {
	smin(segMin[id] , val);
	smin(segMax[id] , val);
}

inline void shift(int id) {
	applyMin(lid , segMax[id]);
	applyMin(rid , segMax[id]);
	applyMax(lid , segMin[id]);
	applyMax(rid , segMin[id]);
	segMin[id] = 0;
	segMax[id] = 1e5;
}

void segApplyMin(int s, int t, int val , int l = 0 , int r = n2 , int id = 1) {
	if (l >= s && r <= t) {
		applyMin(id , val);
		return;
	}
	int mid = l + r >> 1;
	shift(id);
	if (s < mid) segApplyMin(s  ,t , val , l , mid , lid);
	if (t > mid) segApplyMin(s , t , val , mid , r , rid);
}

void segApplyMax(int s, int t, int val , int l = 0 , int r = n2 , int id = 1) {
	if (l >= s && r <= t) {
		applyMax(id , val);
		return;
	}
	int mid = l + r >> 1;
	shift(id);
	if (s < mid) segApplyMax(s  ,t , val , l , mid , lid);
	if (t > mid) segApplyMax(s , t , val , mid , r , rid);
}
int res[N];

void dfs(int l = 0, int r = n2, int id = 1) {
	if (l == r - 1) {
		res[l] = segMin[id];
	//	cout << l << ' '<< segMin[id] << ' '<< segMax[id] << endl;
		return;
	}
	int mid= l +r >> 1;
	shift(id);
	dfs(l , mid, lid);
	dfs(mid ,r, rid);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

	n2 = n;

	fill(segMax , segMax + (N << 2) , 1e5 + 1);

	rep(i , 0 , k) 
		op[i] == 1 ? 
			segApplyMax(left[i] , right[i] + 1 , height[i]) :
			segApplyMin(left[i] , right[i] + 1 , height[i]);
//	cout << "DONE" << endl;

	dfs();

	memcpy(finalHeight , res , 4 * n2);

	return;
}

Compilation message

wall.cpp: In function 'void segApplyMin(int, int, int, int, int, int)':
wall.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wall.cpp: In function 'void segApplyMax(int, int, int, int, int, int)':
wall.cpp:55:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wall.cpp: In function 'void dfs(int, int, int)':
wall.cpp:68:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid= l +r >> 1;
           ~~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31608 KB Output is correct
2 Correct 31 ms 31736 KB Output is correct
3 Correct 30 ms 31736 KB Output is correct
4 Correct 35 ms 31992 KB Output is correct
5 Correct 36 ms 31992 KB Output is correct
6 Correct 34 ms 31992 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31608 KB Output is correct
2 Correct 202 ms 39440 KB Output is correct
3 Correct 240 ms 35448 KB Output is correct
4 Correct 640 ms 41432 KB Output is correct
5 Correct 343 ms 41976 KB Output is correct
6 Correct 328 ms 42104 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31652 KB Output is correct
2 Correct 32 ms 31712 KB Output is correct
3 Correct 30 ms 31656 KB Output is correct
4 Correct 35 ms 31992 KB Output is correct
5 Correct 33 ms 31992 KB Output is correct
6 Correct 34 ms 31992 KB Output is correct
7 Correct 29 ms 31608 KB Output is correct
8 Correct 219 ms 39516 KB Output is correct
9 Correct 240 ms 35340 KB Output is correct
10 Correct 642 ms 41560 KB Output is correct
11 Correct 342 ms 42068 KB Output is correct
12 Correct 326 ms 41920 KB Output is correct
13 Correct 29 ms 31608 KB Output is correct
14 Correct 208 ms 39684 KB Output is correct
15 Correct 66 ms 32632 KB Output is correct
16 Correct 719 ms 41812 KB Output is correct
17 Correct 336 ms 41720 KB Output is correct
18 Correct 333 ms 41716 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31608 KB Output is correct
2 Correct 31 ms 31736 KB Output is correct
3 Correct 30 ms 31608 KB Output is correct
4 Correct 36 ms 31992 KB Output is correct
5 Correct 34 ms 31992 KB Output is correct
6 Correct 33 ms 31992 KB Output is correct
7 Correct 37 ms 31684 KB Output is correct
8 Correct 203 ms 39672 KB Output is correct
9 Correct 241 ms 35448 KB Output is correct
10 Correct 637 ms 41464 KB Output is correct
11 Correct 341 ms 41980 KB Output is correct
12 Correct 325 ms 41976 KB Output is correct
13 Correct 28 ms 31608 KB Output is correct
14 Correct 207 ms 39524 KB Output is correct
15 Correct 65 ms 32632 KB Output is correct
16 Correct 708 ms 41820 KB Output is correct
17 Correct 335 ms 41720 KB Output is correct
18 Correct 334 ms 41876 KB Output is correct
19 Correct 740 ms 81852 KB Output is correct
20 Correct 737 ms 87676 KB Output is correct
21 Correct 759 ms 92192 KB Output is correct
22 Correct 732 ms 87800 KB Output is correct
23 Correct 732 ms 87800 KB Output is correct
24 Correct 767 ms 87928 KB Output is correct
25 Correct 744 ms 87900 KB Output is correct
26 Correct 744 ms 92280 KB Output is correct
27 Correct 743 ms 92360 KB Output is correct
28 Correct 730 ms 87908 KB Output is correct
29 Correct 730 ms 87796 KB Output is correct
30 Correct 732 ms 87640 KB Output is correct