Advertisement
Guest User

Untitled

a guest
Aug 25th, 2019
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.57 KB | None | 0 0
  1. #include <math.h>
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <cmath>
  8. #include <deque>
  9. #include <queue>
  10. #include <algorithm>
  11. #include <iterator>
  12. #include <bitset>
  13. #include <iomanip>
  14. #include <functional>
  15. #include <list>
  16. #include <cctype>
  17. #include <ctime>
  18. #include <stack>
  19. using namespace std;
  20.  
  21. #define int int64_t
  22.  
  23. struct Segment {
  24. int start;
  25. int end;
  26. int id;
  27. };
  28.  
  29. signed main() {
  30. int n;
  31. cin >> n;
  32. vector<Segment> s(n);
  33. for (int i = 0; i < n; i++) {
  34. cin >> s[i].start >> s[i].end;
  35. s[i].id = i;
  36. }
  37. int q;
  38. cin >> q;
  39. vector<int> d(q);
  40. for (int i = 0; i < q; i++) {
  41. cin >> d[i];
  42. }
  43. stack<Segment> r;
  44. vector<int> ans(d.size(),-1);
  45. vector<int> used(d.size(), 1);
  46. for (int i = 0; i < s.size(); i++) {
  47. if (r.empty() || (r.top().start <= s[i].start && r.top().end >= s[i].end)) {
  48. r.push(s[i]);
  49. }
  50. else {
  51. while (!(r.empty()) && !(r.top().start <= s[i].start && r.top().end >= s[i].end)) {
  52. int start = r.top().start;
  53. int end = r.top().end;
  54. int id = r.top().id;
  55. int left = 0, right = d.size(), mid;
  56. while (right - left > 1) {
  57. mid = (left + right) / 2;
  58. if (d[mid] > start) {
  59. right = mid;
  60. }
  61. else if (d[mid] < start) {
  62. left = mid;
  63. }
  64. else {
  65. break;
  66. }
  67. }
  68. int f;
  69. if (d[mid] == start) {
  70. f = mid;
  71. }
  72. else if (abs(d[left] - start) < abs(d[right] - start) && d[left] >= start) {
  73. f = left;
  74. }
  75. else {
  76. f = right;
  77. }
  78. while (f > 0 && d[f] == d[f - 1]) {
  79. f--;
  80. }
  81. while (d[f] <= end) {
  82.  
  83. if (used[f] != -1) {
  84. ans[f] = id + 1;
  85. used[f] = -1;
  86.  
  87. }
  88. f++;
  89. }
  90. r.pop();
  91. }
  92. r.push(s[i]);
  93. }
  94. }
  95. while (!r.empty()) {
  96. int start = r.top().start;
  97. int end = r.top().end;
  98. int id = r.top().id;
  99. int left = 0, right = d.size(), mid;
  100. while (right - left > 1) {
  101. mid = (left + right) / 2;
  102. if (d[mid] > start) {
  103. right = mid;
  104. }
  105. else if (d[mid] < start) {
  106. left = mid;
  107. }
  108. else {
  109. break;
  110. }
  111. }
  112. int f;
  113. if (d[mid] == start) {
  114. f = mid;
  115. } else if (abs(d[left] - start) < abs(d[right] - start) && d[left] >= start) {
  116. f = left;
  117. }
  118. else {
  119. f = right;
  120. }
  121. while (f > 0 && d[f] == d[f - 1]) {
  122. f--;
  123. }
  124. while (f < d.size() && d[f] <= end) {
  125.  
  126. if (used[f] != -1) {
  127. ans[f] = id + 1;
  128. used[f] = -1;
  129.  
  130. }
  131. f++;
  132.  
  133. }
  134. r.pop();
  135. }
  136. for (int i = 0; i < ans.size(); i++) {
  137. cout << ans[i] << endl;
  138. }
  139. return 0;
  140. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement