oj.uz

Submission #62634

# Submission time Handle Problem Language Result Execution time Memory
62634 2018-07-29T14:30:32 Z nvmdava Wall (IOI14_wall) C++17
0 / 100
 288 ms 49512 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;


#define SIZE 2097155

int a[4 * SIZE], maxLazy[4 * SIZE], minLazy[4 * SIZE];

void down(int id){
	if(maxLazy[id] == 0){
		if(minLazy[id] == 2147483647){
			return;
		}
		if(id >= 2097152){
			a[id] = min(a[id],minLazy[id]);
			minLazy[id] = 2147483647;
			return;
		}
		minLazy[id << 1] = minLazy[id];
		minLazy[id << 1 | 1] = minLazy[id];
		minLazy[id] = 2147483647;
	} else {
		
		if(id >= 2097152){
			a[id] = max(a[id],maxLazy[id]);
			maxLazy[id] = 0;
			return;
		}
		maxLazy[id << 1] = maxLazy[id];
		maxLazy[id << 1 | 1] = maxLazy[id];
		maxLazy[id] = 0;
	}
}

void find(int id, int x){
	if(maxLazy[id] == 0) a[id] = min(a[id],minLazy[id]); 
	else a[id] = max(a[id],maxLazy[id]);
	if(x == 1){
		return;
	}
	find(id, x >> 1);
}

void maximum(int id, int l, int r, int L, int R, int val){
	down(id);
	if(l == L && r == R){
		maxLazy[id] = val;
		return;
	}
	int m = (l + r) >> 1;
	if(m >= R){
		maximum(id << 1, l, m, L, R, val);
	} else if( m < L){
		maximum(id << 1 | 1, m + 1, r, L, R ,val);
	} else {
		maximum(id << 1, l, m, L, m, val);
		maximum(id << 1 | 1, m + 1, r, m + 1, R ,val);
	}
	
}


void minimum(int id, int l, int r, int L, int R, int val){
	down(id);
	if(l == L && r == R){
		minLazy[id] = val;
		return;
	}
	int m = (l + r) >> 1;
	if(m >= R){
		minimum(id << 1, l, m, L, R, val);
	} else if( m < L){
		minimum(id << 1 | 1, m + 1, r, L, R ,val);
	} else {
		minimum(id << 1, l, m, L, m, val);
		minimum(id << 1 | 1, m + 1, r, m + 1, R ,val);
	}
	
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	
	int i;
	memset(minLazy,2147483647,sizeof(minLazy));
	
	for(i = 0; i < k; i++){
		if(op[i] == 1) maximum(1, 0, 2097151, left[i], right[i], height[i]);
		else minimum(1, 0, 2097151, left[i], right[i], height[i]);
	}
	
	for(i = 1; i < 4194304; i++){
		down(i);
	}
	n += 2097152;
	for(i = 2097152 ; i < n; i++){
		find(i, i);
		finalHeight[i  - 2097152] = a[i]; 
	}
	return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 41336 KB Output is correct
2 Correct 59 ms 41444 KB Output is correct
3 Incorrect 61 ms 41516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 41560 KB Output is correct
2 Correct 288 ms 49512 KB Output is correct
3 Incorrect 230 ms 49512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 49512 KB Output is correct
2 Correct 59 ms 49512 KB Output is correct
3 Incorrect 57 ms 49512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 49512 KB Output is correct
2 Correct 60 ms 49512 KB Output is correct
3 Incorrect 66 ms 49512 KB Output isn't correct
4 Halted 0 ms 0 KB -