Submission #516714

#	Time	Username	Problem	Language	Result	Execution time	Memory
516714		pavement	Wall (IOI14_wall)	C++17	100 / 100	743 ms	231340 KiB

wall

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

int res[2000005];

struct node {
	node *left, *right;
	int S, E, lo, hi;
	node(int _s, int _e) : S(_s), E(_e), lo(0), hi(100000) {
		if (S == E) return;
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
	}
	void s_upd(int v, int ty) {
		if (ty == 1) {
			if (v > hi) lo = hi = v;
			else lo = max(lo, v);
		} else {
			if (v < lo) lo = hi = v;
			else hi = min(hi, v);
		}
	}
	void prop() {
		if (S == E) return;
		left->s_upd(lo, 1);
		left->s_upd(hi, 2);
		right->s_upd(lo, 1);
		right->s_upd(hi, 2);
		lo = 0;
		hi = 100000;
	}
	void upd(int l, int r, int v, int ty) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			s_upd(v, ty);
			return;
		}
		prop();
		left->upd(l, r, v, ty);
		right->upd(l, r, v, ty);
	}
	void trav() {
		if (S == E) {
			res[S] = lo;
			return;
		}
		prop();
		left->trav();
		right->trav();
	}
} *root;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	root = new node(0, n - 1);
	for (int i = 0; i < k; i++)
		root->upd(left[i], right[i], height[i], op[i]);
	root->trav();
	for (int i = 0; i < n; i++) finalHeight[i] = res[i];
}

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