oj.uz

Submission #736937

# Submission time Handle Problem Language Result Execution time Memory
736937 2023-05-06T11:27:58 Z NeroZein Wall (IOI14_wall) C++17
0 / 100
 1 ms 212 KB 
#include "wall.h"
#include "bits/stdc++.h"
using namespace std; 
#define lx (nd * 2)
#define rx (nd * 2 + 1)

const int N = 2000006;

struct node {
	int mn = 0, mx = 0; 
};

node seg[N << 1]; 

void push (int nd) {
	for (int i = lx; i < lx + 2; ++i) {
		seg[i].mn = min(seg[i].mn, seg[nd].mn); 
		seg[i].mn = max(seg[i].mn, seg[nd].mx); 
		seg[i].mx = min(seg[i].mx, seg[nd].mn);
		seg[i].mx = max(seg[i].mx, seg[nd].mx); 
	}
}

void upd (int nd, int l, int r, int s, int e, int v, int op) {
	if (l > e || r < s) {
		return; 
	}
	if (l >= s && r <= e) {
		if (op == 1) {
			seg[nd].mx = max(seg[nd].mx, v); 
			seg[nd].mn = max(seg[nd].mn, v); 
		} else {
			seg[nd].mx = min(seg[nd].mx, v); 
			seg[nd].mn = min(seg[nd].mn, v); 
		}
		return; 
	}
	push(nd);
	seg[nd].mn = N; 
	seg[nd].mx = 0; 
	int mid = (l + r) >> 1;
	upd(lx, l, mid, s, e, v, op);
	upd(rx, mid + 1, r, s, e, v, op); 
}

inline void dive (int nd, int l, int r) {
	if (l == r) {
		assert(seg[nd].mn == seg[nd].mx); 
		cout << seg[nd].mn << ' '; 
		return; 
	}
	push(nd); 
	int mid = (l + r) >> 1;
	dive(lx, l, mid);
	dive(rx, mid + 1, r); 
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for (int i = 0; i < k; ++i) {
		upd(1, 0, n - 1, left[i], right[i], height[i], op[i]);
	}	
	dive(1, 0, n - 1); 
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -