Segment Tree Implementation

Revision en2, by Iwaskid, 2017-02-02 06:36:51

Hi all, I am trying to code up a solution to the "Seating" problem in USACO January 2013 Gold, which uses a segment tree with lazy propagation. My code passes the first 2 test cases, but fails the rest. I have checked multiple times about my code but I don't see the problem.

#include<iostream>
#include<fstream>
#include<algorithm>
#include<assert.h>
#include<string>
#include<vector>
using namespace std;
int n, m;
int t;
vector<int> A;
vector<int> l0, r0, lazy0, lazy1,ans;

void build(int a,int l,int r) {
	if (r - l < 1) {
		l0[a] = 1;
		r0[a] = 1;
		ans[a] = 1;
		return;
	}
	l0[a] = r - l + 1;
	r0[a] = r - l + 1;
	ans[a] = r - l + 1;
	build(a * 2, l, (r + l) / 2);
	build(a * 2 + 1, (r + l) / 2 + 1, r);
}
void lazyupdate(int a,int l,int r) {
	assert(!(lazy0[a]==1&& lazy1[a]));
	if (lazy0[a]) {
		lazy0[a] = 0;
		l0[a] =ans[a]= r - l + 1;
		r0[a] = r - l + 1;
		if (l != r) { lazy0[2 * a] = 1; lazy0[2 * a + 1] = 1; lazy1[2 * a] = 0; lazy1[2 * a + 1] = 0; }
	}
	else if (lazy1[a]) {
		l0[a] = ans[a]=r0[a] = 0;
		if (l != r) { lazy1[2 * a] = 1; lazy1[2 * a + 1] = 1; lazy0[2 * a] = 0; lazy0[2 * a + 1] = 0; }
		lazy1[a] = 0;
	}
}
void updateint(int a, int l, int r) {
	int left = 2 * a, right = 2 * a + 1;
	l0[a] = ans[a] = r0[a] = 0;
	if (l0[left] == ((l + r) / 2 - l + 1)) {
		l0[a] = max(l0[a], max(l0[left], l0[left] + l0[right]));
	}
	else l0[a] = max(l0[a], l0[left]);
	if (r0[right] == (r - (l + r) / 2)) {
		r0[a] = max(r0[a], r0[right] + r0[left]);
	}
	else r0[a] = max(l0[a], r0[right]);
	ans[a] = max(r0[a], max(l0[a], r0[left] + l0[right]));
}
void update0(int i, int j,int a=1, int l=0, int r=n-1) {
	lazyupdate(a, l, r);
	if (j<l || i>r)return;
	
	if (l >= i&&r <= j) {
		l0[a] = r - l + 1;
		r0[a] =ans[a]= r - l + 1;
		if (l == r)return;
		lazy0[2 * a] = 1; lazy0[2 * a + 1] = 1;
		lazy1[2 * a] = 0; lazy1[2 * a + 1] = 0;
		return;
	}
	int left = 2 * a, right = 2 * a + 1;
	update0(i, j, left, l, (l + r) / 2);
	update0(i, j, right, (l + r) / 2 + 1, r);
	updateint(a, l, r);

}
void update1(int i, int j, int a = 1, int l = 0, int r = n - 1) {
	lazyupdate(a, l, r);
	if (j<l || i>r)return;

	if (l >= i&&r <= j) {
		l0[a] = 0;
		r0[a] = 0;
		ans[a] = 0;
		if (l == r)return;
		lazy1[2 * a] = 1; lazy1[2 * a + 1] = 1; 
		lazy0[2 * a] = 0; lazy0[2 * a + 1] = 0;
		return;
	}
	int left = 2 * a, right = 2 * a + 1;
	update1(i, j, left, l, (l + r) / 2);
	update1(i, j, right, (l + r) / 2 + 1, r);
	updateint(a, l, r);
}
pair<int,int> getint(int num, int a = 1, int l = 0, int r = n - 1) {
	lazyupdate(a, l, r);
	if(l!=r)lazyupdate(2 * a, l, (l + r) / 2);
	if(l!=r)lazyupdate(2 * a + 1, (l + r) / 2 + 1, r);
	if (ans[a] == num&&r-l+1==num) {
		return pair<int, int>(l, r);
	}
	int left = 2 * a, right = 2 * a + 1;
	if (ans[left] >= num) {
		return getint(num, a * 2, l, (l + r) / 2);
	}

	if (r0[left] + l0[right] >= num&&r0[left]!=0) {
			int need = num - r0[left];
			pair<int, int> p1;
			p1.first = (l + r) / 2 - r0[left] + 1;
			p1.second = (l + r) / 2 + need;
			
			return p1;
	}
	if (ans[right]>=num) {
		return getint(num, a * 2 + 1, (l + r) / 2 + 1, r);
	}
	assert(0);
}
int main() {
	ifstream fin("seating.in");
	ofstream fout("seating.out");
	fin >> n >> m;
	l0, r0, lazy0, lazy1, ans;
	A.resize(n);
	l0.resize(4 * n); r0.resize(4 * n); lazy0.resize(4 * n); lazy1.resize(4 * n); ans.resize(4 * n);
	build(1, 0, n - 1);
	int res = 0;
	for (int i = 0; i < m; i++) {

		string stat;
		fin >> stat;
		if (stat[0] == 'A') {
			int add; fin >> add;
			if (ans[1] < add) {
				res++;
				continue;
			}
			pair<int, int> p = getint(add);
			update1(p.first, p.second);
		}
		else {
			int from, to; fin >> from >> to;
			from--; to--;
			update0(from, to);
		}
	}
	fout << res << endl;
	return 0;
}

In my segment tree, update0 updates a given range of values to 0,update1 updates a given range of values to 1, updateint updates the interval whenever some of its values have changed.getInt(add) gets the lowest position to insert the group of people. lazy0 andlazy1 stores respectively the lazy propagation for setting to 0 and setting to 1. Thank you so much for your help.

Tags c++, data structures, segment tree, lazy propagation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Iwaskid 2017-02-03 03:36:49 19
en3 English Iwaskid 2017-02-02 06:37:13 0 (published)
en2 English Iwaskid 2017-02-02 06:36:51 0 (saved to drafts)
en1 English Iwaskid 2017-02-02 06:35:00 4367 Initial revision (published)