Cod sursa(job #814776)

Utilizator toranagahVlad Badelita toranagah Data 16 noiembrie 2012 02:44:23
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");
const int MAX_N = 100100;
struct seg {
	int left, right, current, lenght;
} segTree[MAX_N * 3];
int N, P;

void buildSegTree(int node, int lo, int hi);
void updateSegTree(int node, int lo, int hi, int a, int b, int action);
void mergeSeg(int node);

int main() {
	fin >> N >> P;
	buildSegTree(1, 1, N);
	for (int i = 1; i <= P; ++i) {
		int action;
		fin >> action;
		if (action == 3) {
			fout << segTree[1].current << '\n';
		} else {
			int a, dim;
			fin >> a >> dim;
			updateSegTree(1, 1, N, a, a + dim - 1, action);
		}
	}
	return 0;
}

void buildSegTree(int node, int lo, int hi) {
	if (lo == hi) {
		segTree[node].left = segTree[node].right = 1;
		segTree[node].current = segTree[node].lenght = 1;
	} else {
		int mid = lo + (hi - lo) / 2;
		buildSegTree(node * 2, lo, mid);
		buildSegTree(node * 2 + 1, mid + 1, hi);
		mergeSeg(node);
	}
}

void mergeSeg(int node) {
	int s1 = node * 2;
	int s2 = node * 2 + 1;
	segTree[node].lenght = segTree[s1].lenght + segTree[s2].lenght;
	segTree[node].left = segTree[s1].left;
	if (segTree[s1].left == segTree[s1].lenght) {
		segTree[node].left += segTree[s2].left;
	}
	segTree[node].right = segTree[s2].right;
	if (segTree[s2].right == segTree[s2].lenght) {
		segTree[node].right += segTree[s1].right;
	}
	segTree[node].current = max(segTree[s1].right + segTree[s2].left,
									max(segTree[s1].current, segTree[s2].current));
}

void updateSegTree(int node, int lo, int hi, int a, int b, int action) {
	if (lo >= a && b >= hi) {
		if (action == 1) {
			segTree[node].left = segTree[node].right = segTree[node].current = 0;
		} else {
			segTree[node].left = segTree[node].right = segTree[node].lenght;
			segTree[node].current = segTree[node].lenght;
		}
	} else {
		int s1 = node * 2;
		int s2 = node * 2 + 1;
		int mid = lo + (hi - lo) / 2;
		if (segTree[node].left == segTree[node].right
		   && segTree[node].left == segTree[node].current) {
			if (segTree[node].left == 0) {
				segTree[s1].left = segTree[s1].right = segTree[s1].current = 0;
				segTree[s2].left = segTree[s2].right = segTree[s2].current = 0;
			} else if (segTree[node].left == segTree[node].lenght) {
				segTree[s1].left = segTree[s1].right = segTree[s1].lenght;
				segTree[s1].current = segTree[s1].lenght;
				segTree[s2].left = segTree[s2].right = segTree[s2].lenght;
				segTree[s2].current = segTree[s2].lenght;
			}
		}
		if (a <= mid) {
			updateSegTree(s1, lo, mid, a, b, action);
		}
		if (b > mid) {
			updateSegTree(s2, mid + 1, hi, a, b, action);
		}
		mergeSeg(node);
	}
}