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

問題

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

問題概要

N個の教室とM個の清掃区間がある。
このうちいくつかの清掃区間はほかの清掃区間と被っていて
清掃する必要がない。
そのような清掃区間の数と、区間番号を出力する。

解法

まずimos法を使って各教室が何個の清掃区間と被っているかをで求める。
次に平方分割でQuery(x,y) := [x,y]の清掃区間の被覆数の最小値をで求めれるようにして、各清掃区間についてQuery(x,y)を求め、1以下のものを列挙すればで答えを求めることができる。

公式スライドのほうがコード量少ない&簡単→
AtCoder Regular Contest 045 解説

コード

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>

#define INF 100000000
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long

using namespace std;

#define MAX_N 300005
#define MAX_M 100005

int N, M;
int S[MAX_M], T[MAX_M];
int Sum[MAX_N];
int DSum[600];

bool Input(){

	cin >> N >> M;
	for (int i = 0; i < M; i++){
		cin >> S[i] >> T[i];
	}

	return true;

}

void Calc(){

	memset(Sum, 0, sizeof(Sum));
	fill(DSum, DSum+600, INF);

	for (int i = 0; i < M; i++){
		Sum[S[i]]++;
		Sum[T[i] + 1]--;
	}

	for (int i = 1; i <= N+1; i++){
		Sum[i] += Sum[i - 1];
	}

	for (int i = 1; i <= N; i++){
		int x = i / 600;
		DSum[x] = min(DSum[x], Sum[i]);
	}

}

//[x,y]の最小値
int Query(int x, int y){

	if (x > y)
		swap(x, y);

	int ret = INF;

	if (y - x < 600){
		while (x <= y){
			ret = min(ret, Sum[x]);
			x++;
		}
		return ret;
	}
	
	while (x % 600 != 0){
		ret = min(ret, Sum[x]);
		x++;
	}
	ret = min(ret, Sum[x]);
	while (y % 600 != 0){
		ret = min(ret, Sum[y]);
		y--;
	}
	ret = min(ret, Sum[y]);
	while (x < y){
		ret = min(ret, DSum[x / 600]);
		x += 600;
	}

	return ret;

}

int ansCnt = 0;
int ansList[MAX_M];

void Solve(){

	ansCnt = 0;

	for (int i = 0; i < M; i++){
		if (Query(S[i], T[i]) > 1){
			ansList[ansCnt] = i + 1;
			ansCnt++;
		}
	}

	cout << ansCnt << endl;
	for (int i = 0; i < ansCnt; i++){
		cout << ansList[i] << endl;
	}

}

int main(){

	Input();

	Calc();

	Solve();

	return 0;

}