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;
}