Submission #1635908

---

Source Code Expand

#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

static const int MAX_SIZE = 1 << 19; //segment tree のサイズ。この実装では2べきにする必要がある。 2^17 ≒ 1.3 * 10^5

typedef long long Int;
Int segMin[2 * MAX_SIZE - 1], segAdd[2 * MAX_SIZE - 1];

//区間[a, b)に値xを加算する.
void add(int a, int b, int x, int k = 0, int l = 0, int r = MAX_SIZE)
{
    if (r <= a || b <= l) return; //もし交差しない区間であれば終える.
    
    if (a <= l && r <= b){ //もし今みている区間[l, r)が[a, b)に完全に内包されていれば
        segAdd[k] += x;  //区間[l, r)にkを加算する.
        return;
    }
    
    add(a, b, x, k * 2 + 1, l, (l + r) / 2); //子の区間に(必要があれば)xを加算する.
    add(a, b, x, k * 2 + 2, (l + r) / 2, r); //〃

    //親の区間の最小値は, 子の区間の最小値 + 自分に一様に加算されている値 である.一様に加算される値は更新しなくて良い.
    segMin[k] = min(segMin[k * 2 + 1] + segAdd[k * 2 + 1], segMin[k * 2 + 2] + segAdd[k * 2 + 2]);
}

Int getMin(int a, int b, int k = 0, int l = 0, int r = MAX_SIZE)
{
    if (r <= a || b <= l) return (LLONG_MAX);
    
    if (a <= l && r <= b) return (segMin[k] + segAdd[k]); //完全に内包されていれば,その区間の最小値を返す.
    
    Int left = getMin(a, b, k * 2 + 1, l, (l + r) / 2); //子の区間の最小値を求める.
    Int right = getMin(a, b, k * 2 + 2, (l + r) / 2, r); //子の区間の最小値を求める
    
    return (min(left, right) + segAdd[k]); //親の区間の最小値は, 子の区間の最小値 + 自分に一様に加算されている値 である (大切なので2回書きました!!)
    
}



int main(){
#ifdef LOCAL_TEST
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    // cerr << "Start" << endl;
    int n, m;
    cin >> n >> m;
    vi s(m), t(m);
    rep(i, m) {
        cin >> s[i] >> t[i];
        s[i]--;
        add(s[i], t[i], 1);
    }
    if(getMin(0, n) == 0) {
        cout << 0 << endl;
        return 0;
    }
    vector<int> ans;
    rep(i, m) {
        add(s[i], t[i], -1);
        // cerr << s[i] << " " << t[i] << " " << getMin(s[i], t[i]) << endl;
        if(getMin(s[i], t[i]) != 0) ans.pb(i+1);
        add(s[i], t[i], +1);
    }
    cout << ans.size() << endl;
    for(auto& a : ans) cout << a << endl;
    return 0;
}

Submission Info

Judge Result