Guest User

Untitled

a guest
Apr 20th, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4. #include <algorithm>
  5. #include <set>
  6. #define INF 2000000000
  7. using namespace std;
  8.  
  9. #define BEGIN true
  10. #define END false
  11.  
  12. #define CIVN(i) timeline[i].second
  13. #define IS_BEGIN(i) (timeline[i].first.second == BEGIN)
  14. #define IS_END(i) (timeline[i].first.second == END)
  15. #define TIME(i) (timeline[i].first.first)
  16.  
  17. int N;
  18. vector< pair<pair<int, bool>, int> > timeline;
  19.  
  20. int main() {
  21.     cin >> N;
  22.     for (int i = 0; i < N; i++) {
  23.                 int i1, i2;
  24.                 cin >> i1 >> i2;
  25.                 if (i1 != i2) {
  26.                         timeline.push_back(make_pair(make_pair(i1, BEGIN), i));
  27.                         timeline.push_back(make_pair(make_pair(i2, END), i));
  28.                 }
  29.     }
  30.     sort(timeline.begin(), timeline.end());
  31.     int c = 0;
  32.     int min_interval = INF;
  33.     int result1, result2;
  34.     int background = -1;
  35.         int prev_background;
  36.     for (int i = 0; i < timeline.size(); i++) {
  37.                 if (IS_BEGIN(i)) {
  38.                         prev_background = background;
  39.                         background = CIVN(i);
  40.                         c++;
  41.                 }
  42.                 else {
  43.                         c--;
  44.                         if (c == 0) continue;
  45.                         if (IS_END(i-1)) continue;
  46.                         int nv = TIME(i) - TIME(i-1);
  47.                         if (nv != 0 && nv < min_interval) {
  48.                                 result1 = CIVN(i);
  49.                                 if (CIVN(i) == CIVN(i-1))
  50.                                         result2 = prev_background;
  51.                                 else result2 = CIVN(i-1);
  52.                                 min_interval = nv;
  53.                         }
  54.                 }
  55.     }
  56.     if (min_interval == INF)
  57.                 cout << 0 << endl;
  58.     else {
  59.                 cout << min(result1, result2) + 1 << ' ' << max(result1, result2) + 1 << endl;
  60.     }
  61.     return 0;
  62. }
Add Comment
Please, Sign In to add comment