Submission #3431629

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll n, m, s[100100], t[100100], room[300100], lim[300100];
vector<ll> one, ans;
int main(void){
    // Your code here!
    cin >> n >> m;
    for (ll i = 1; i <= m; i++){
        cin >> s[i] >> t[i];
        room[s[i]]++, room[t[i] + 1]--;
    }
    for (ll i = 1; i < n; i++) room[i + 1] += room[i];
    for (ll i = 1; i <= n; i++) {
        if (room[i] == 1) one.push_back(i);
    }
    if (one.size() == 0){
        cout << m << endl;
        for (ll i = 1; i <= m; i++) cout << i << endl;
        return 0;
    }
    for (ll i = 1; i < one[0]; i++){
        lim[i] = one[0] - 1;
    }
    for (ll i = 1; i < one.size(); i++){
        for (ll j = one[i - 1] + 1; j < one[i]; j++){
            lim[j] = one[i] - 1;
        }
    }
    for (ll i = one[one.size() - 1] + 1; i <= n; i++){
        lim[i] = n;
    }
    for (ll i = 1; i <= m; i++){
        if (lim[s[i]] >= t[i] && room[s[i]] > 1) ans.push_back(i);
    }
    cout << ans.size() << endl;
    for (ll i = 0; i < ans.size(); i++){
        cout << ans[i] << endl;
    }
}

Submission Info

Judge Result