Submission #385429

#	Time	Username	Problem	Language	Result	Execution time	Memory
385429		aarr	Wall (IOI14_wall)	C++14	100 / 100	1378 ms	91776 KiB

wall

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

const int N = 2000 * 1000 + 5;
int n;

pair <int, int> smin[N * 4], smax[N * 4];

void apply(int id, int qt, int h, int t) {
	if (t == 0) {
		return;
	}
	if (qt == 1) {
		if (h < smax[id].first && smin[id].second > smax[id].second && smin[id].first < h) {
			smax[id] = {h, t};
		}
		else {
			smax[id] = max(smax[id], {h, t});
		}
	}
	else {
		if (h >= smin[id].first && smin[id].second < smax[id].second && smax[id].first > h) {
			smin[id] = {h, t};
		}
		else {
			smin[id] = min(smin[id], {h, t});
		}
	}	
}

void shift(int id) {
	if (smin[id].second <= smax[id].second) {
		apply(id * 2, 2, smin[id].first, smin[id].second);
		apply(id * 2, 1, smax[id].first, smax[id].second);
		apply(id * 2 + 1, 2, smin[id].first, smin[id].second);
		apply(id * 2 + 1, 1, smax[id].first, smax[id].second);
	}
	else {
		apply(id * 2, 1, smax[id].first, smax[id].second);
		apply(id * 2, 2, smin[id].first, smin[id].second);
		apply(id * 2 + 1, 1, smax[id].first, smax[id].second);
		apply(id * 2 + 1, 2, smin[id].first, smin[id].second);
	}
	
	
	smin[id] = {N, 0};
	smax[id] = {0, 0};
}

void update(int qt, int l, int r, int h, int t, int id = 1, int s = 0, int e = n) {
	if (r <= s || e <= l) {
		return;
	}
	if (l <= s && e <= r) {
	//	cout << "72 " << id << " " << s << " " << e << " " << l << " " << r << endl;
		apply(id, qt, h, t);
		return;
	}
	int md = (s + e) / 2;
	shift(id);
	update(qt, l, r, h, t, id * 2, s, md);
	update(qt, l, r, h, t, id * 2 + 1, md, e);
}

int get(int p, int id = 1, int s = 0, int e = n) {
	if (e - s == 1) {
		if (smax[id].second >= smin[id].second || smax[id].first <= smin[id].first) {
			return smax[id].first;
		}
		return smin[id].first;
	}
	shift(id);
	int md = (s + e) / 2;
	if (p < md) {
		return get(p, id * 2, s, md);
	}
	return get(p, id * 2 + 1, md, e);
}


void buildWall(int m, int q, int op[], int left[], int right[], int height[], int finalHeight[]){
	n = m;
	for (int i = 0; i < q; i++) {
		update(op[i], left[i], right[i] + 1, height[i], i + 1);
	}
	for (int i = 0; i < n; i++) {
		finalHeight[i] = get(i);
	}
}

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