제출 #425941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425941		SuhaibSawalha1	Wall (IOI14_wall)	C++17	100 / 100	920 ms	69536 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 2e6;
int seg[4 * N], seg2[4 * N], n;

void pull (int idx, int d, int u) {
	seg[idx] = min(seg[idx], d);
	seg[idx] = max(seg[idx], u);
	seg2[idx] = max(seg2[idx], u);
	seg2[idx] = min(seg2[idx], d);
}

void push_down (int idx) {
	pull(2 * idx, seg[idx], seg2[idx]);
	pull(2 * idx + 1, seg[idx], seg2[idx]);
	seg[idx] = 1e9;
	seg2[idx] = 0;
}

#define mid (L + R) / 2
void update (int st, int en, int h, int t, int idx = 1, int L = 0, int R = n - 1) {
	if (L > en || R < st) {
		return;
	}
	if (L >= st && R <= en) {
		pull(idx, t == 1 ? 1e9 : h, t == 1 ? h : 0);
		return;
	}
	push_down(idx);
	update(st, en, h, t, 2 * idx, L, mid);
	update(st, en, h, t, 2 * idx + 1, mid + 1, R);
}

void query (int idx, int L, int R, int f[]) {
	if (L == R) {
		f[L] = seg[idx];
		return;
	}
	push_down(idx);
	query(2 * idx, L, mid, f);
	query(2 * idx + 1, mid + 1, R, f);
}

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

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