JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Binary Indexed Trees more sample problems
 more sample problems | Reply I think this article will be nice add problems to sample problems.I post here some problems i hope to admins or writer refer to this post :)Moofest(USACO) - http://acm.pku.edu.cn/JudgeOnline/problem?id=1990Moible Phones(IOI) - http://acm.pku.edu.cn/JudgeOnline/problem?id=1195Teams(BOI) - http://infoman.musala.com/boi/2004/team.pdf
 Re: more sample problems (response to post by libe) | Reply thanks for the problems...so i was trying to solve the 1195 problem from PKU```#include   using namespace std; int n; int v[1025][1025]; void Add(int idx, int idy, int S) { int y2 = idy; while (idx <= n) { idy = y2; while ( idy <= n ) { v[idx][idy] += S; idy +=(idy & -idy); } idx += (idx & -idx); } } int querry(int idx, int idy) { int y2 = idy; int ret = 0; while (idx > 0) { idy = y2; while ( idy > 0 ) { ret += v[idx][idy]; idy -= (idy & -idy); } idx -= (idx & -idx); } return ret; } int main() { while (1) { int command; scanf("%d", &command); if ( command == 3 ) return 0; if ( command == 0 ) scanf("%d", &n); if ( command == 1 ) { int x, y, a; scanf("%d %d %d", &x, &y, &a); Add(x, y, a); } if ( command == 2 ) {int l, b, r, t; scanf("%d %d %d %d", &l, &b, &r, &t); int total = 0; total = querry(r, t) - querry(l-1, t) - querry(r, b-1) + querry(l-1 ,b-1); printf("%d\n", total); } } return 0; }   ```and is TLE-ing ...any one know what is wrong??
 Re: more sample problems (response to post by vlad_D) | Reply You used 1-base index version of Binary Indexed Tree and the rows and columns are 0-base index.Add "++idx; ++idy;" in the begin of "Add" and "querry" function to get AC.
 Re: more sample problems (response to post by ktuan) | Reply oh, that's right!
 Re: more sample problems (response to post by libe) | Reply There's one BIT solution in the practice rooms for SRM 315 Div 2 900.
 Re: more sample problems (response to post by libe) | Reply I post here some problems i hope to admins or writer refer to this post :)I wanted to add some problems from SPOJ, but admins didn't allow me that. It probably because I didn't find more problems from TopCoder and as I understood admins, it is not point to refer problems from other sites. But it is great you have added some links through forum. Thank you.
 Re: more sample problems (response to post by libe) | Reply SPOJ::MATSUMThis is a problem identical to one that author used in his example for 2d-BIT...
 Re: more sample problems (response to post by libe) | Reply Blocked Road (TJU) - http://acm.tju.edu.cn/toj/showp3243.html
 Re: more sample problems (response to post by MarioYC) | Reply Here are the problems in SPOJ which i did with BIT spoj HORRIBLEspoj ORDERSspoj CTRICKspoj MATSUM This s from Codechef.com/NOV10/Problem is BOMBING nice problem we have to use compression technique :)
 Re: more sample problems (response to post by libe) | Reply A "recent" TC semifinal problem : http://www.topcoder.com/stat?c=problem_statement&pm=11120&rd=14285
 Re: more sample problems (response to post by vexorian) | Reply A problem from our yesterdays contest http://www.codechef.com/CMUTANTS/problems/TEMPQUE/EDIT: I have added this to spoj http://www.spoj.pl/problems/TEMPLEQ/
 Re: more sample problems (response to post by ktuan) | Reply Hello! May I ask you a private problem?Where are you from? Which college？
 Forums Tutorial Discussions Binary Indexed Trees more sample problems Previous Thread  |  Next Thread