処理時間心配だったけどどうにか通った。
https://yukicoder.me/problems/no/2687
問題
1次元座標上で、N+M個の雲が存在している。
各雲はある範囲を覆っており、時刻0における座標が与えられる。
うちN個は時速1で右方向、残りM個は時速1で左方向に移動する。
ここでK個の座標が与えられる。その座標で、同時に2個以上の雲に覆われる時間帯があるか判定せよ。
なお、時刻は負の場合も考えてよい。
解法
もし同じ方向に動く雲で、時刻0で共通部分がある場合、その共通部分は全部の位置を通る。
そのようなケースはあらかじめ求めておこう。
そうでない場合、N*M通りの雲の組み合わせに対し、共通部分が生じる位置が存在する。
K個の座標のうち、そこに含まれるものをmapなどで高速に検索しよう。
int N,M; pair<ll,ll> A[101010]; pair<ll,ll> B[101010]; int ret[1010]; int K; ll P[1010]; map<ll,int> Ps; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N) { cin>>A[i].first>>A[i].second; A[i].first*=2; A[i].second*=2; } FOR(i,M) { cin>>B[i].first>>B[i].second; B[i].first*=2; B[i].second*=2; } sort(A,A+N); sort(B,B+M); ll R=-1LL<<60; int ok=0; FOR(i,N) { if(A[i].first<=R) ok=1; R=max(R,A[i].second); A[i].first-=1LL<<50; A[i].second-=1LL<<50; } R=-1LL<<60; FOR(i,M) { if(B[i].first<=R) ok=1; R=max(R,B[i].second); B[i].first+=1LL<<50; B[i].second+=1LL<<50; } cin>>K; FOR(i,K) { cin>>P[i]; P[i]*=2; if(ok) { ret[i]=1; } else { Ps[P[i]]=i; } } FOR(x,N) FOR(y,M) { ll L=(A[x].first+B[y].first)/2; ll R=(A[x].second+B[y].second)/2; while(1) { auto it=Ps.lower_bound(L); if(it==Ps.end()||it->first>R) break; ret[it->second]=1; Ps.erase(it); } } FOR(i,K) cout<<ret[i]<<" "; cout<<endl; }
まとめ
最初に行う、同じ向きの雲の重複部分を求める処理の方が面倒かも。