Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- typedef long long ll;
- typedef pair<int, int> pii;
- #define X first
- #define Y second
- #define popcount __builtin_popcount
- #define popcountll __builtin_popcountll
- // change type to pair & use counter for multi-set
- typedef tree<
- int,
- null_type,
- less<int>,
- rb_tree_tag,
- tree_order_statistics_node_update>
- ordered_set;
- void fastInOut();
- const double EPS = 1e-9;
- const int MOD = 1e9 + 7;
- const int N = 2e5 + 5;
- pii rng[N];
- bool cmp(const pii &p1, const pii &p2)
- {
- if(p1.X == p2.X)
- return p1.Y > p2.Y;
- return p1.X < p2.X;
- }
- int main() {
- //freopen("input.txt", "r", stdin);
- //freopen("out.txt", "w", stdout);
- fastInOut();
- int n, m;
- cin >> n >> m;
- for(int i=0; i<n; ++i)
- cin >> rng[i].X >> rng[i].Y;
- sort(rng, rng + n, cmp);
- if(rng[0].X != 1) {
- cout << "NO\n";
- return 0;
- }
- priority_queue<pii> have;
- vector<int> used;
- used.push_back(1);
- int reach = rng[0].Y;
- int cnt = 1;
- for(int i=0; i<n; ++i) {
- if(rng[i].X <= reach) {
- have.push({rng[i].Y, i+1});
- } else {
- if(rng[i].X == reach + 1) {
- have.push({rng[i].Y, i+1});
- }
- if(!have.empty()) {
- reach = max(reach, have.top().X);
- used.push_back(have.top().Y);
- have.pop();
- cnt++;
- }
- if(reach < rng[i].X)
- break;
- have.push({rng[i].Y, i+1});
- }
- }
- if(reach < m && !have.empty()) {
- reach = max(reach, have.top().X);
- used.push_back(have.top().Y);
- cnt++;
- }
- if(reach < m) cout << "NO\n";
- else {
- cout << "YES\n" << cnt << '\n';
- for(int i : used)
- cout << i << ' ';
- cout << '\n';
- }
- return 0;
- }
- void fastInOut() {
- ios_base::sync_with_stdio(0);
- cin.tie(NULL), cout.tie(NULL);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement