Advertisement
Guest User

Untitled

a guest
Mar 4th, 2015
188
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. int iteration = 0;
  8. int const max_number_of_stars = 15000;
  9.  
  10.  
  11. int n; // number of stars
  12. int amount_on_levels[max_number_of_stars + 1][20];
  13.  
  14.  
  15. vector<int> t;
  16. int tn;
  17.  
  18. void init(int nn)
  19. {
  20. tn = nn;
  21. t.assign(tn, 0);
  22. }
  23.  
  24. int sum(int r)
  25. {
  26. int result = 0;
  27. for (; r >= 0; r = (r & (r + 1)) - 1)
  28. result += t[r];
  29. return result;
  30. }
  31.  
  32. void inc(int i, int delta)
  33. {
  34. for (; i < tn; i = (i | (i + 1)))
  35. t[i] += delta;
  36. }
  37.  
  38. int sum(int l, int r)
  39. {
  40. return sum(r) - sum(l - 1);
  41. }
  42.  
  43. void init(vector<int> a)
  44. {
  45. init((int)a.size());
  46. for (unsigned i = 0; i < a.size(); i++)
  47. inc(i, a[i]);
  48. }
  49.  
  50.  
  51. int main() {
  52. iostream::sync_with_stdio(false);
  53. while (cin >> n) {
  54. init(32001);
  55. for (int i = 0; i < n; ++i) {
  56. int x, y;
  57. cin >> x >> y;
  58.  
  59. amount_on_levels[sum(x)][iteration] += 1;
  60. inc(x, 1);
  61. }
  62.  
  63. for (int i = 0; i < n; ++i) {
  64. cout << amount_on_levels[i][iteration] << endl;
  65. }
  66.  
  67. ++iteration;
  68.  
  69. }
  70.  
  71. return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement