Hello 2020 : D. New Year and Conference

ようやく2020年。
https://codeforces.com/contest/1284/problem/D

問題

N個の授業が、A,B2つの会場で1回ずつ行われる。
その際、授業の開始時間・終了時間が与えられる。

ある授業の集合が場所依存であるとは、全部をAで受けたときと全部をBで受けたとき、片方では授業時間の重なりがなく片方ではある場合を示す。
入力に対し、場所依存の集合があるか判定せよ。

解法

まず時間を座標圧縮しておく。
Aを時間順に走査し、Aにおいて重ならない範囲の授業間において、Bで重なりが生じるかをBITを使って判定しよう。
その後A,Bを反転させて同じ処理をもう一度行う。

int N;
int S[2][202020],E[2][202020];
vector<int> add[404040],del[404040];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> BS,BE;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<int> X;
	X.push_back(0);
	FOR(i,N) {
		cin>>S[0][i]>>E[0][i]>>S[1][i]>>E[1][i];
		E[0][i]++;
		E[1][i]++;
		X.push_back(S[0][i]);
		X.push_back(S[1][i]);
		X.push_back(E[0][i]);
		X.push_back(E[1][i]);
	}
	sort(ALL(X));
	X.erase(unique(ALL(X)),X.end());
	FOR(i,N) {
		S[0][i]=lower_bound(ALL(X),S[0][i])-X.begin();
		E[0][i]=lower_bound(ALL(X),E[0][i])-X.begin();
		S[1][i]=lower_bound(ALL(X),S[1][i])-X.begin();
		E[1][i]=lower_bound(ALL(X),E[1][i])-X.begin();
	}
	FOR(j,2) {
		FOR(i,N) {
			add[S[0][i]].push_back(i);
			del[E[0][i]].push_back(i);
		}
		FOR(i,404040) {
			FORR(e,del[i]) {
				if(BE(S[1][e])) return _P("NO\n");
				if(BS((1<<19)-1)-BS(E[1][e]-1)) return _P("NO\n");
			}
			FORR(e,del[i]) {
				BS.add(S[1][e],-1);
				BE.add(E[1][e],-1);
			}
			FORR(e,add[i]) {
				BS.add(S[1][e],1);
				BE.add(E[1][e],1);
			}
			add[i].clear();
			del[i].clear();
		}
		FOR(i,N) {
			swap(S[0][i],S[1][i]);
			swap(E[0][i],E[1][i]);
		}
	}
	
	cout<<"YES"<<endl;
	
}

まとめ

問題文の解釈に手間取った記憶が。