Submission #5903393

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>



using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)




















 
int main(){
    ll n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> v(m);
    REP(i, m){
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end());
    v.push_back({INF, INF});
    priority_queue<ll> que;
    ll t = 0, p = 0, ans = 0;
    for(ll i = 1; i <= n; i++){
        while(v[p].first <= i){
            que.push({v[p++].second});
        }
        if(t < i){
            if(que.empty() || que.top() < i){
                cout << "Impossible" << endl;
                return 0;
            }
            t = que.top();
            ans++;
        }
    }
    cout << ans << endl;
}

Submission Info

Judge Result