Advertisement
Guest User

Untitled

a guest
Sep 15th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. typedef long long ll;
  9. typedef pair<int, int> pii;
  10. #define X first
  11. #define Y second
  12. #define popcount __builtin_popcount
  13. #define popcountll __builtin_popcountll
  14. // change type to pair & use counter for multi-set
  15. typedef tree<
  16.     int,
  17.     null_type,
  18.     less<int>,
  19.     rb_tree_tag,
  20.     tree_order_statistics_node_update>
  21.     ordered_set;
  22.  
  23. void fastInOut();
  24. const double EPS = 1e-9;
  25. const int MOD = 1e9 + 7;
  26. const int N = 2e5 + 5;
  27.  
  28. pii rng[N];
  29.  
  30. bool cmp(const pii &p1, const pii &p2)
  31. {
  32.     if(p1.X == p2.X)
  33.         return p1.Y > p2.Y;
  34.     return p1.X < p2.X;
  35. }
  36.  
  37. int main() {
  38.     //freopen("input.txt", "r", stdin);
  39.     //freopen("out.txt", "w", stdout);
  40.     fastInOut();
  41.     int n, m;
  42.     cin >> n >> m;
  43.     for(int i=0; i<n; ++i)
  44.         cin >> rng[i].X >> rng[i].Y;
  45.     sort(rng, rng + n, cmp);
  46.     if(rng[0].X != 1) {
  47.         cout << "NO\n";
  48.         return 0;
  49.     }
  50.     priority_queue<pii> have;
  51.     vector<int> used;
  52.     used.push_back(1);
  53.     int reach = rng[0].Y;
  54.     int cnt = 1;
  55.     for(int i=0; i<n; ++i) {
  56.         if(rng[i].X <= reach) {
  57.             have.push({rng[i].Y, i+1});
  58.         } else {
  59.             if(rng[i].X == reach + 1) {
  60.                 have.push({rng[i].Y, i+1});
  61.             }
  62.             if(!have.empty()) {
  63.                 reach = max(reach, have.top().X);
  64.                 used.push_back(have.top().Y);
  65.                 have.pop();
  66.                 cnt++;
  67.             }
  68.             if(reach < rng[i].X)
  69.                 break;
  70.             have.push({rng[i].Y, i+1});
  71.         }
  72.     }
  73.     if(reach < m && !have.empty()) {
  74.         reach = max(reach, have.top().X);
  75.         used.push_back(have.top().Y);
  76.         cnt++;
  77.     }
  78.     if(reach < m) cout << "NO\n";
  79.     else {
  80.         cout << "YES\n" << cnt << '\n';
  81.         for(int i : used)
  82.             cout << i << ' ';
  83.         cout << '\n';
  84.     }
  85.     return 0;
  86. }
  87.  
  88. void fastInOut() {
  89.     ios_base::sync_with_stdio(0);
  90.     cin.tie(NULL), cout.tie(NULL);
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement