Advertisement
Guest User

Untitled

a guest
Dec 10th, 2018
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstring>
  5. using namespace std;
  6.  
  7. int n; // size of heap
  8. long m[200000]; // heap
  9.  
  10. struct gruz{
  11. int l, t;
  12. };
  13.  
  14. bool operator > (gruz g, gruz f){
  15. return g.t > f.t;
  16. }
  17.  
  18. bool operator < (gruz g, gruz f){
  19. return g.t < f.t;
  20. }
  21.  
  22. bool operator <= (gruz g, gruz f){
  23. return g.t <= f.t;
  24. }
  25.  
  26. bool operator >= (gruz g, gruz f){
  27. return g.t >= f.t;
  28. }
  29.  
  30. void SiftUp(int i){
  31. if (i > 1){
  32. if (m[i] < m[i / 2]) {
  33. swap(m[i], m[i / 2]);
  34. SiftUp((i / 2));
  35. }
  36. }
  37. }
  38.  
  39. void insert(long a){
  40. ++n;
  41. m[n] = a;
  42. int i = n;
  43. SiftUp(i);
  44. }
  45.  
  46. void SiftDown(int i){
  47. if (n >= 2 * i + 1){
  48. if (m[2 * i] > m[2 * i + 1]){
  49. if (m[2 * i + 1] < m[i]) {
  50. swap(m[2 * i + 1], m[i]);
  51. SiftDown(2 * i + 1);
  52. }
  53. }
  54. else {
  55. if (m[2 * i] < m[i]) {
  56. swap(m[2 * i], m[i]);
  57. SiftDown(2 * i);
  58. }
  59. }
  60. }
  61. else if (n == 2 * i){
  62. if (m[2 * i] < m[i]){
  63. swap(m[2 * i], m[i]);
  64. SiftDown(2 * i);
  65. }
  66. }
  67. }
  68.  
  69. void extract_min(){
  70. if (n > 0) {
  71. long min = m[1];
  72. m[1] = m[n];
  73. --n;
  74. if (n > 0) SiftDown(1);
  75. }
  76. }
  77.  
  78.  
  79. int main() {
  80. int N;
  81. cin >> N;
  82. gruz g[N];
  83. int Max = 0;
  84. for (int i = 0; i < N; ++i){
  85. cin >> g[i].t >> g[i].l;
  86. Max = max(Max, g[i].l + g[i].t);
  87. }
  88. sort(g, g + N);
  89. int count = 0;
  90. int answer = -1;
  91. for (int i = 0; i <= Max; ++i){
  92. if (n > 0){
  93. while (n > 0 && m[1] == i) extract_min();
  94. }
  95. while (count < N && g[count].t == i){
  96. insert(g[count].t + g[count].l);
  97. count++;
  98. }
  99. answer = max(answer, n);
  100. }
  101. cout << answer;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement