Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2018
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.93 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. return;
  24. }
  25. else {
  26. m = (l + r) / 2;
  27. if (znach < vec[m]) {
  28. binpoisk(znach, l, m, vec);
  29. }
  30. else if (znach>vec[m]) {
  31. binpoisk(znach, m, r, vec);
  32. }
  33. else {
  34. poisk = m;
  35. return;
  36. }
  37. }
  38. }
  39. bool ssrt(pair <ll, bool> a, pair<ll, bool>b) {
  40. t++;
  41. cout << a.first << " " << b.first << endl;
  42. if (a.first > b.first) {
  43. return 0;
  44. }
  45. else {
  46. return 1;
  47. }
  48. }
  49. int main() {
  50. ll a, b, res1 = 0, m, c, n, i, j, k, l;
  51. freopen("in1.txt", "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. poisk = -1;
  95. if (res.size() > 0) {
  96. poisk = -1;
  97. binpoisk(a, -1, res.size() - 1, res.data());
  98. if (poisk < res.size() && res[poisk] > a)poisk -= 1;
  99. }vivod.pb((res.size() - poisk - 1) * 2 + res1);
  100. }
  101. }
  102. for (i = 0; i < vivod.size(); ++i) {
  103. cout << vivod[i] << endl;
  104. }
  105. return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement