fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define N_TESTS 10
  3. #define LSOne(x) (x & (-x))
  4.  
  5. using namespace std;
  6.  
  7. vector<int> ft, v;
  8.  
  9. int rsq(int x) {
  10. 	int ans = 0;
  11. 	for(; x; x -= LSOne(x)) ans += ft[x];
  12. 	return ans;
  13. }
  14.  
  15. int rsq(int a, int b) {
  16. 	return rsq(b) - rsq(a-1);
  17. }
  18.  
  19. void update(int x, int inc) {
  20. 	for(; x<(signed)ft.size(); x+=LSOne(x)) ft[x]+=inc;
  21. }
  22.  
  23. int main() {
  24. 	srand (time(NULL));
  25. 	for(int test=1; test<=N_TESTS; test++) {
  26.         printf("Test %d",test);
  27. 		int n = (rand() % 100) + 1;
  28. 		ft.resize(n+1);
  29. 		v.resize(n+1);
  30. 		fill(ft.begin(), ft.end(), 0);
  31. 		for(int i=1; i<=n; i++) v[i] = rand()%100, update(i, v[i]);
  32. 		for(int i=1; i<=n; i++) {
  33. 			for(int j=i; j<=n; j++) {
  34. 				int ans = 0;
  35. 				for(int k=i; k<=j; k++) ans += v[k];
  36. 				assert(ans == rsq(i,j));
  37. 			}
  38. 		}
  39.         printf(" - PASS\n");
  40. 	}
  41. }
  42.  
Success #stdin #stdout 0s 3456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Test 1 - PASS
Test 2 - PASS
Test 3 - PASS
Test 4 - PASS
Test 5 - PASS
Test 6 - PASS
Test 7 - PASS
Test 8 - PASS
Test 9 - PASS
Test 10 - PASS
https://ideone.com/8UWmlF
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!