IOI 2001 Mobiles: RE

Hi. I was trying to solve this problem which came in IOI 2001: http://wcipeg.com/problems/desc/ioi0111

I have used 2D BIT/Fenwick Tree and simple IEP for 2 sets. I am getting RE for all the test cases though I can’t figure out the reason. It’s working fine on the sample case provided. Here is my code:

(On the WCIPEG website, it says: ‘a.out: error while l’)

#include<iostream>
using namespace std;

int a[1026][1026];
int n;
int ftree[1026][1026];

void updatey(int,int,int);
int querytreey(int,int);

void update(int i, int j, int val)
{
	while(i <= n)
	{
		updatey(i,j,val);
		i += i&(-i);
	}
	return;
}

void updatey(int i, int j, int val)
{
	while(j <= n)
	{
		ftree[i][j] += val;
		j += j&(-j);
	}
	return;
}

int querytree(int i, int j)
{
	int ans = 0;
	while(i > 0)
	{
		ans += querytreey(i,j);
		i -= i&(-i);
	}
	return ans;
}

int querytreey(int i, int j)
{	int ans = 0;
	while(j > 0)
	{
		ans += ftree[i][j];
		j -= j&(-j);
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	int temp;
	cin >> temp >> n;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)
			a[i][j] = 0;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)
			update(i,j,a[i][j]);
	int q;
	while(1)
	{
		cin >> q;
		if(q == 1)
		{
			int x,y,lul;
			cin >> x >> y >> lul;
			update(x+1,y+1,lul);
		}
		if(q == 2)
		{
			int l,b,r,t;
			cin >> l >> b >> r >> t;
			++l;++b;++r;++t;
			cout << querytree(r,t)-querytree(r,b-1)-querytree(l-1,t)+querytree(l-1,b-1) << '\n';
		}
		if(q == 3)
			break;
	}
	return 0;
}

Also, I have used 1 based indexing.

Another irony. The same code gives 100 points on SPOJ: http://www.spoj.com/OI/status/ketanhwr/

1 Like