제출 #986922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986922		Muaath_5	벽 (IOI14_wall)	C++17	0 / 100	3078 ms	8548 KiB

wall

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 2e6+1;

struct seg {
	int val, op, lazy;
} tree[4*N];

int sz;

void pushdown(int node, int l, int r) {
	if (tree[node].op) {
	
		if (tree[node].op == 1) {
			tree[node].val = max(tree[node].val, tree[node].lazy);
			if (l < r) {
				tree[node*2].lazy = max(tree[node*2].lazy, tree[node].lazy);
				tree[node*2].op = tree[node].op;
				tree[node*2+1].lazy = max(tree[node*2].lazy, tree[node].lazy);
				tree[node*2+1].op = tree[node].op;
			}
		}
		else if (tree[node].op == 2) {
			tree[node].val = min(tree[node].val, tree[node].lazy);
			if (l < r) {
				tree[node*2].lazy = min(tree[node*2].lazy, tree[node].lazy);
				tree[node*2].op = tree[node].op;
				tree[node*2+1].lazy = min(tree[node*2].lazy, tree[node].lazy);
				tree[node*2+1].op = tree[node].op;
			}
		}
			
			
		
		tree[node].op = 0;
	}
}

void update(int ql, int qr, int h, int o, int l=0, int r=N-1, int node=1) {
	pushdown(node, l, r);
	if (r < ql || l > qr) return;
	if (ql <= l && r <= qr) {
		tree[node].op = o;
		tree[node].lazy = h;
		pushdown(node, l, r);
		return;
	}
	
	const int mid = (l+r)/2;
	update(ql, qr, h, o, l, mid, node*2);
	update(ql, qr, h, o, mid+1, r, node*2+1);
}

void build(int* arr, int l=0, int r=N-1, int node=1) {
	pushdown(node, l, r);
	if (l == r) {
		if (l < sz)
			arr[l] = tree[node].val;
		return;
	}
	const int mid = (l+r)/2;
	build(arr, l, mid, node*2);
	build(arr, mid+1, r, node*2+1);
}

void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[])
{
	sz=n;
	for (int tq = 0; tq < q; tq++) {
		if (tq && op[tq] == 2 && op[tq-1] == 1) {
			build(finalHeight);
		}
		update(left[tq], right[tq], height[tq], op[tq]);
	}
	build(finalHeight);
}

#ifdef MUAATH_5
int main()
{
  int n;
  int k;

  int i, j;  
  int status = 0;

  status = scanf("%d%d", &n, &k);
  assert(status == 2);

  int* op = (int*)calloc(sizeof(int), k);
  int* left = (int*)calloc(sizeof(int), k);
  int* right = (int*)calloc(sizeof(int), k);
  int* height = (int*)calloc(sizeof(int), k);
  int* finalHeight = (int*)calloc(sizeof(int), n);

  for (i = 0; i < k; i++){
    status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    assert(status == 4);
  }

  buildWall(n, k, op, left, right, height, finalHeight);

  for (j = 0; j < n; j++)
    printf("%d\n", finalHeight[j]);
  
  return 0;
}

#endif

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39