AtCoder Regular Contest 045 B - ドキドキデート大作戦高橋君

本番書いたコードがなぜ通っているのかよくわかってない。でも通れば正義。
今まで見た ARC B 問題の中では一番むずかしい気がします。

問題

arc045.contest.atcoder.jp

解法

解説の通りやってみました。

AtCoder Regular Contest 045 解説 from AtCoder Inc.

www.slideshare.net

const int MAXN = 300300;
int s[100010], t[100010];
int imos[MAXN];
int cnt[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> s[i] >> t[i];
        imos[s[i]] += 1;
        imos[t[i]+1] += -1;
    }
    int now = 0;
    for (int i = 1; i < MAXN; i++) {
        imos[i] += now;
        now = imos[i];
        cnt[i] = cnt[i-1];
        if (imos[i] > 1) cnt[i] += 1;
    }
    vector<int> ans;
    for (int i = 0; i < M; i++) {
        if (cnt[t[i]] - cnt[s[i]-1] == t[i]-s[i]+1) ans.push_back(i+1);
    }
    cout << ans.size() << endl;
    for (int el : ans) cout << el << endl;
    return 0;
}