Блог пользователя Iwaskid

Автор Iwaskid, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Iwaskid (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Iwaskid (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I think you would be lucky to get a direct response to this post from someone willing to read all of the code and pinpoint the bug. Also, it's better to figure it out yourself and develop your debugging skills.

I would start by finding a test case on which the program produces a wrong answer. Create a few small cases, solve them by hand, and check if your program's output matches your expectations. Make sure you hit all the edge cases. Based on the problem statement, I would guess you can make a case with 4 intervals or fewer that will hit your bug.

Once you have the test case, debugging will be a lot more straightforward. Maybe you will already realize the bug, just from seeing what the wrong answer is. If not, you can start debugging the code methodically. You could, for example, print the state of the segment tree after every event, and check that the printed values match your expectations. As soon as you see that they don't, you can dig further into the specific event that broke your logic, and eventually isolate the bug.

Good luck!