Advertisement
achulkov2

Untitled

Mar 11th, 2018
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.38 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. const int INF = static_cast<int>(2e9) + 1;
  9.  
  10. struct segment {
  11. int l, r;
  12. };
  13.  
  14. int main() {
  15. int n;
  16. cin >> n;
  17. vector<segment> v(n);
  18. vector<pair<pair<int, int>, int>> events;
  19. for (int i = 0; i < n; ++i) {
  20. cin >> v[i].l >> v[i].r;
  21. events.push_back({{v[i].l, 1}, i});
  22. events.push_back({{v[i].r, 0}, i});
  23. }
  24. sort(events.begin(), events.end());
  25. set<pair<int, int>> opened;
  26. int ans = INF;
  27. int a = 0, b = 0;
  28. int balance = 0;
  29. for (int i = 0; i < 2 * n; ++i) {
  30. int x = events[i].first.first;
  31. int type = events[i].first.second;
  32. int index = events[i].second;
  33. if (type == 0) {
  34. if (balance > 0) ans = min(v[index].r - v[index].l, ans);
  35. opened.erase({v[index].l, index});
  36. if (!opened.empty()) {
  37. auto p = *(--opened.end());
  38. if (x - p.first < ans) {
  39. ans = x - p.first;
  40. a = index, b = p.second;
  41. }
  42. }
  43. } else if (type == 1) {
  44. opened.insert({x, index});
  45. }
  46. }
  47. if (ans != INF) {
  48. if (a > b) swap(a, b);
  49. cout << a + 1 << " " << b + 1 << "\n";
  50. } else {
  51. cout << "0\n";
  52. }
  53. return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement