Submission #1014088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014088		DorostWef	Wall (IOI14_wall)	C++17	100 / 100	487 ms	166228 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;
#define F first
#define S second

const int N = 500012, SegN = (1 << 20), INF = 1e7 + 190; 
pair <int, int> seg[SegN];
vector <int> s[N * 4], e[N * 4]; 
pair <int, int> p[N];
int kk = 0;

void build (int v = 1, int tl = 0, int tr = kk - 1) {
	seg[v] = {INF, -INF};
	if (tl != tr) {
		int mid = (tl + tr) >> 1;
		build (v << 1, tl, mid);
		build (v << 1 | 1, mid + 1, tr);
	}
}

pair <int, int> Merge (pair <int, int> p, pair <int, int> q) {
	pair <int, int> w;
	if (q.F >= p.F)
		w = p;
	else if (q.F <= p.S) {
		w = {q.F, q.F};
	} else {
		w = {q.F, p.S};
	}
	w.S = max (w.S, q.S);
	if (w.F <= w.S)
		w = {w.S, w.S};
	return w;
}

void upd (int i, int a, int b, int v = 1, int tl = 0, int tr = kk - 1) {
	if (tl == tr) {
		seg[v].F = a;
		seg[v].S = b;
		return;
	}
	int mid = (tl + tr) >> 1;
	if (i <= mid)
		upd (i, a, b, v << 1, tl, mid);
	else
		upd (i, a, b, v << 1 | 1, mid + 1, tr);
	seg[v] = Merge (seg[v << 1], seg[v << 1 | 1]);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	kk = k;
	build();
	for (int i = 0; i < k; i++) {
		s[left[i]].push_back(i);
		e[right[i]].push_back(i);
		if (op[i] == 1) {
			p[i].S = height[i];
			p[i].F = INF;
		} else {
			p[i].F = height[i];
			p[i].S = -INF;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j : s[i]) {
			upd (j, p[j].F, p[j].S);
		}
		int x = 0;
		x = min (x, seg[1].F);
		x = max (x, seg[1].S);
		finalHeight[i] = x;
		for (int j : e[i]) {
			upd (j, INF, -INF);
		}
	}
}

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