martarubtsova

Untitled

Feb 23rd, 2018
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <string>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. vector < int > answer;
  9.  
  10. int f(int x, vector < int > v)
  11. {
  12.     int max = -INT_MIN, max_i;
  13.     if (x < int(v.size()) - 1)
  14.     {
  15.         for (int i = x + 1; i < int(v.size()); i++)
  16.             if (v[i] > max)
  17.                 max = v[i] + 1;
  18.     }
  19.     else
  20.         max = 0;
  21.     return max;
  22. }
  23.  
  24. void w(int x, vector <int > v, vector < int > c)
  25. {
  26.     int max = -1, max_i;
  27.     for (int i = x + 1; i < int(v.size()); i++)
  28.         if (c[i] >= max)
  29.         {
  30.             max = c[i];
  31.             max_i = i;
  32.         }
  33.     answer.push_back(max_i);
  34.     if (c[max_i] > 0)
  35.         w(v[max_i], v, c);
  36. }
  37. int main()
  38. {
  39.     int n, x, y;
  40.     vector < pair < int, int > > a;
  41.     vector < pair < int, int > > coordinate;
  42.     vector < int > b;
  43.     cin >> n;
  44.     for (int i = 0; i < n; i++)
  45.     {
  46.         cin >> x >> y;
  47.         a.push_back(make_pair(x, y));
  48.     }
  49.     sort(a.begin(), a.end());
  50.     for (int i = 0; i < n; i++)
  51.     {
  52.         coordinate.push_back(make_pair(a[i].first, i));
  53.         coordinate.push_back(make_pair(a[i].second, i));
  54.     }
  55.     sort(coordinate.begin(), coordinate.end());
  56.     int open = 0;
  57.     for (int i = 0; i < n * 2; i++)
  58.     {
  59.         if (int(b.size()) <= coordinate[i].second)
  60.         {
  61.             b.push_back(-1);
  62.             open = coordinate[i].second;
  63.         }
  64.         else
  65.             b[coordinate[i].second] = open;
  66.     }
  67.     vector < int > c = b;
  68.     for (int i = int(b.size()) - 1; i >= 0; i--)
  69.             c[i] = f(b[i], c);
  70.     c[0] += 1;
  71.     int max = -1, max_i;
  72.     for (int i = 0; i < n; i++)
  73.         if (c[i] > max)
  74.         {
  75.             max = c[i];
  76.             max_i = i;
  77.         }
  78.     answer.push_back(max_i);
  79.     w(b[max_i], b, c);
  80.     cout << answer.size() << endl;
  81.     for (int i = 0; i < int(answer.size()); i++)
  82.         cout << a[answer[i]].first << ' '<< a[answer[i]].second << endl;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment