AtCoder Regular Contest 045 B - ドキドキデート大作戦高橋君
本番書いたコードがなぜ通っているのかよくわかってない。でも通れば正義。
今まで見た ARC B 問題の中では一番むずかしい気がします。
解法
解説の通りやってみました。
www.slideshare.netconst 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; }