Submission #20204846

---

Source Code Expand

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

int main()
{
  int n, m;
  cin >> n >> m;

  vector<int> v(n);
  vector<int> s(n);
  vector<int> t(n);

  // Imos 法で各教室の被覆数を求める
  for (int i = 0; i < m; i++){
    cin >> s[i] >> t[i]; s[i]--; t[i]--;
    v[s[i]]++;
    if (t[i] < n-1) v[t[i]+1]--;
  }
  for (int i = 1; i < n; i++){
    v[i] += v[i-1];
  }

  // 被覆数=1 の教室のみ 1 にする
  for (int i = 0; i < n; i++){
    if (v[i] != 1) v[i] = 0;
  }

  // さらに累積和
  for (int i = 1; i < n; i++){
    v[i] += v[i-1];
  }

  vector<int> ans;
  for (int i = 0; i < m; i++){
    int a = v[t[i]];
    if (s[i] > 0) a -= v[s[i]-1];
    if (a  == 0) ans.push_back(i+1);
  }

  cout << ans.size() << endl;
  for (int i : ans) cout << i << endl;
  return 0;
}

Submission Info

Judge Result