Advertisement
Guest User

Untitled

a guest
Feb 29th, 2020
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5.  
  6. using namespace __gnu_pbds;
  7. using namespace std;
  8.  
  9. //#pragma comment(linker, "/stack:200000000")
  10. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  11.  
  12. #pragma GCC optimize("unroll-loops")
  13. #pragma GCC optimize("Ofast")
  14. #pragma GCC optimize("-O")
  15. #pragma GCC optimize("-s")
  16. #pragma GCC optimize("-Os")
  17. #pragma GCC optimize("-O1")
  18. #pragma GCC optimize("-O2")
  19. #pragma GCC optimize("-O3")
  20.  
  21. #define ll long long
  22. #define ld long double
  23. #define int ll
  24. #define F first
  25. #define S second
  26. #define pb push_back
  27. #define pf push_front
  28. #define endl '\n'
  29. #define TIME 1.0*clock()/CLOCKS_PER_SEC
  30. #define pii pair<int, int>
  31. #define Tip pii
  32.  
  33. typedef tree< Tip, null_type, less<Tip>, rb_tree_tag, tree_order_statistics_node_update> ord_set;
  34.  
  35. #ifdef SashOK
  36. #else
  37. #define cerr if(0)cerr
  38. #endif
  39.  
  40. const int inf = 1e9;
  41.  
  42. main() {
  43. ios_base::sync_with_stdio(0);
  44. cin.tie(0);
  45. cout.tie(0);
  46. #ifdef SashOK
  47. freopen("input.txt", "r", stdin);
  48. freopen("output.txt", "w", stdout);
  49. #else
  50. // freopen("input.txt", "r", stdin);
  51. // freopen("output.txt", "w", stdout);
  52. // freopen("INPUT.TXT", "r", stdin);
  53. // freopen("OUTPUT.TXT", "w", stdout);
  54. // freopen("forest.in", "r", stdin);
  55. // freopen("forest.out", "w", stdout);
  56. #endif
  57. int n;
  58. cin >> n;
  59. vector<pii> m;
  60. vector<pii> p;
  61. int mm = 0, pp = 0;
  62. int ODIN = 0;
  63. int ans = 0;
  64. for(int i = 0; i < n; i++)
  65. {
  66. int x, t;
  67. cin >> x >> t;
  68. if(x == 0 && t != 0)
  69. {
  70. ODIN++;
  71. continue;
  72. }
  73. if(x > 0)
  74. {
  75. p.pb({x, t});
  76. }
  77. else
  78. {
  79. m.pb({-x, t});
  80. }
  81. // a.pb({x, t});
  82. }
  83. sort(m.begin(), m.end());
  84. sort(p.begin(), p.end());
  85. int id = 1;
  86. // ord_set mem;
  87. // mem.insert({1, 1});
  88. // mem.insert({2, 2});
  89. // mem.insert({3, 3});
  90. // mem.insert({4, 4});
  91. // cout << mem.order_of_key({2, -1});
  92. // return 0;
  93. /// 1)<- 2)->
  94.  
  95. // for(auto to:m)cout << to.F << ' ' << to.S << endl;
  96. // cout << endl;
  97. // for(auto to:p)cout << to.F << ' ' << to.S << endl;
  98.  
  99. ord_set st1;
  100. for(int i = 0; i < m.size(); i++)
  101. {
  102. if(m[i].S > m[i].F)
  103. {
  104. st1.insert({m[i].S - m[i].F, id});
  105. id++;
  106. }
  107. }
  108. // for(auto to:st1)
  109. // {
  110. // cout << to.F << ' ';
  111. // }
  112. int k1 = 0;
  113. for(int i = 0; i < p.size(); i++)
  114. {
  115. if(p[i].F < p[i].S)
  116. {
  117. k1++;
  118. ans = max(ans, k1 + st1.size() - st1.order_of_key({p[i].F * 2 + 1, -1}));
  119. }
  120. }
  121. /// 1)-> 2)<-
  122. ord_set st2;
  123. for(int i = 0; i < p.size(); i++)
  124. {
  125. if(p[i].S > p[i].F)
  126. {
  127. st2.insert({p[i].S - p[i].F, id});
  128. id++;
  129. }
  130. }
  131. int k2 = 0;
  132. for(int i = 0; i < m.size(); i++)
  133. {
  134. if(m[i].F < m[i].S)
  135. {
  136. k2++;
  137. ans = max(ans, k2 + st2.size() - st2.order_of_key({m[i].F * 2 + 1, 0}));
  138. }
  139. }
  140. int ansver = ans + ODIN;
  141. if(ansver > 0 && ansver % 2 == 0)ansver--;
  142. cout << ansver;
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement