Submission #106668

#	Time	Username	Problem	Language	Result	Execution time	Memory
106668		tincamatei	Wall (IOI14_wall)	C++14	100 / 100	1453 ms	127140 KiB

wall

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

using namespace std;

const int MAX_N = 2000000;
const int MAX_K = 500000;
const int MAX_VAL = 100000;

struct Range {
	int l, r;

	Range():l(0), r(MAX_VAL + 1) {}
	Range(int _l, int _r):l(_l), r(_r) {}

	Range operator+ (const Range &x) const {
		return Range(max(l, x.l), min(r, x.r));
	}
};

Range aint[1+4*MAX_K];

void update(int poz, Range x, int l = 0, int r = MAX_K - 1, int nod = 1) {
	if(poz < l || r < poz) return;

	if(l == r)
		aint[nod] = x;
	else {
		int mid = (l + r) / 2;
		update(poz, x, l, mid, 2 * nod);
		update(poz, x, mid + 1, r, 2 * nod + 1);
		aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
	}
}

bool intersect(const Range &x) {
	return x.l > x.r;
}

int query(Range &x, int l = 0, int r = MAX_K - 1, int nod = 1) {
	if(l == r)
		return l;
	else {
		int mid = (l + r) / 2;
		if(intersect(x + aint[2 * nod + 1]))
			return query(x, mid + 1, r, 2 * nod + 1);
		else {
			x = x + aint[2 * nod + 1];
			return query(x, l, mid, 2 * nod);
		}
	}
}

struct Event {
	Range x;
	int poz;
};

vector<Event> evs[MAX_N + 1];
Range mod[MAX_K];

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = 0; i < k; ++i) {
		if(op[i] == 1)
			evs[left[i]].push_back({Range(height[i], MAX_VAL + 1), i});
		else
			evs[left[i]].push_back({Range(0, height[i]), i});
		evs[right[i] + 1].push_back({Range(), i});
	}

	int rez = 0;

	for(int i = 0; i < n; ++i) {
		for(auto it: evs[i]) {
			update(it.poz, it.x);
			mod[it.poz] = it.x;
		}
		
		if(!evs[i].empty()) {
			Range last = Range();
			int poz;
	
			poz = query(last);
	
			if((last + mod[poz]).l <= last.r)
				rez = (last + mod[poz]).l;
			else if((last + mod[poz]).l > last.r)
				rez = last.r;
			else
				rez = last.l;
		}

		finalHeight[i] = rez;
	}
}

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