Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2018
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.65 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include<iostream>
  4. #include<stack>
  5. #include<vector>
  6. #include<iterator>
  7. #include<cstdio>
  8. #include<algorithm>
  9.  
  10. #define ll long long
  11. #define pb push_back
  12. #define sc second
  13. #define fst first
  14.  
  15. using namespace std;
  16.  
  17. ll poisk, t = 0;
  18.  
  19. void binpoisk(ll znach, ll l, ll r, double *vec) {
  20. ll m;
  21. if (r - l <= 1) {
  22. poisk = r;
  23. /*if (vec[r] == znach || vec[l] == znach || vec[r]>znach) {
  24. poisk = r+1;
  25. }*/
  26. return;
  27. }
  28. else {
  29. m = (l + r) / 2;
  30. if (znach < vec[m]) {
  31. binpoisk(znach, l, m, vec);
  32. }
  33. else {
  34. binpoisk(znach, m, r, vec);
  35. }
  36. }
  37. }
  38. bool ssrt(pair <ll, bool> a, pair<ll, bool>b) {
  39. //t++;
  40. //cout << a.first << " " << b.first << endl;
  41. if (a.first > b.first) {
  42. return 0;
  43. }
  44. else {
  45. return 1;
  46. }
  47. }
  48. int main() {
  49. ll a, b, res1 = 0, m, c, n, i, j, k, l;
  50. //freopen("in.txt", "r", stdin);
  51. freopen("linear.in", "r", stdin);
  52. freopen("linear.out", "w", stdout);
  53. cin >> n;
  54. stack<ll>plus;
  55. stack<ll>minus;
  56. vector<double>res;
  57. vector<ll>vivod;
  58. vector< pair< ll, bool > >vec;
  59. for (i = 0; i < n; ++i) {
  60. cin >> a >> b;
  61. if (b == 1) {
  62. vec.pb(make_pair(a, 1));
  63. }
  64. else {
  65. vec.pb(make_pair(a, 0));
  66. }
  67. }
  68. sort(vec.begin(), vec.end(), ssrt);
  69. for (i = 0; i < n; ++i) {
  70. //если электрон
  71. if (vec[i].sc == 0) {
  72. if (plus.size() == 0) {
  73. res1++;
  74. }
  75. else {
  76. res.pb((vec[i].fst - plus.top()));
  77. res[res.size() - 1] /= 2;
  78. plus.pop();
  79. }
  80. }
  81. else if (vec[i].sc) {
  82. plus.push(vec[i].fst);
  83. }
  84. }
  85. sort(res.begin(), res.end());
  86. res1 += plus.size();
  87. cin >> m;
  88. for (i = 0; i < m; ++i) {
  89. cin >> a;
  90. if (a == 0) {
  91. vivod.pb(vec.size());
  92. }
  93. else {
  94. if ((m == 1 && a >= -100 && a <= 100)||(m>1)) {
  95. poisk = res.size();
  96. if (res.size() > 0) {
  97. poisk = -1;
  98. binpoisk(a, 0, res.size(), res.data());
  99. //if (poisk < res.size() && res[poisk] > a)poisk -= 1;
  100. /*for (j = 0; j < res.size(); ++j) {
  101. if (res[j] > a) {
  102. poisk = j;
  103. j = res.size();
  104. }
  105. }
  106. if (poisk == -1)poisk = res.size();
  107. */
  108. }
  109. vivod.pb((res.size() - poisk) * 2 + res1);
  110. }
  111. else {
  112. poisk = -1;
  113. if (res.size() > 0) {
  114. poisk = -1;
  115. //binpoisk(a, -1, res.size() - 1, res.data());
  116. //if (poisk < res.size() && res[poisk] > a)poisk -= 1;
  117. for (j = 0; j < res.size(); ++j) {
  118. if (res[j] > a) {
  119. poisk = j;
  120. j = res.size();
  121. }
  122. }
  123. if (poisk == -1)poisk = res.size();
  124. }
  125. vivod.pb((res.size() - poisk) * 2 + res1);
  126. }
  127. }
  128. t = 0;
  129. }
  130. for (i = 0; i < vivod.size(); ++i) {
  131. cout << vivod[i] << endl;
  132. }
  133. return 0;
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement