Submission #425781

#	Time	Username	Problem	Language	Result	Execution time	Memory
425781		SuhaibSawalha1	Wall (IOI14_wall)	C++17	24 / 100	708 ms	80936 KiB

wall

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

const int N = 2e6;
int seg[4 * N], lazyR[4 * N], lazyA[4 * N], lazyL[4 * N], n;

void pull (int idx, int a, int r, int l) {
	if (l == 1) {
		seg[idx] = min(seg[idx], r);
		seg[idx] = max(seg[idx], a);
	}
	else {
		seg[idx] = max(seg[idx], a);
		seg[idx] = min(seg[idx], r);
	}
	lazyL[idx] = l;
	lazyA[idx] = max(lazyA[idx], a);
	lazyR[idx] = min(lazyR[idx], r);
}

void push_down (int idx) {
	if (lazyL[idx]) {
		pull(2 * idx, lazyA[idx], lazyR[idx], lazyL[idx]);
		pull(2 * idx + 1, lazyA[idx], lazyR[idx], lazyL[idx]);
		lazyL[idx] = 0;
		lazyA[idx] = -1;
		lazyR[idx] = 2e9;
	}
}

#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 ? h : -1, t == 1 ? 2e9 : h, t);
		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 < 4 * N; ++i) {
		lazyA[i] = -1;
		lazyR[i] = 2e9;
	}
	for (int i = 0; i < k; ++i) {
		update(left[i], right[i], height[i], op[i]);
	}
	query(1, 0, n - 1, finalHeight);
}

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