AtCoder ABC #128 : E - Roadwork

昨日に比べるといまいち。
https://atcoder.jp/contests/abc128/tasks/abc128_e

問題

1次元の数直線上で、ある時刻に原点を出発し、速度1で数直線上正の方向に移動することを考える。
ここでN個の道路工事の状況が与えられる。
各道路工事では、時刻[S,T)内に座標Xで行われる。

以下のクエリQ個の答えよ。

• 時刻Dに出発した場合、最初に道路工事に遭遇する位置はどこか。

解法

時刻[S,T)に座標Xで行われる工事に遭遇するには、出発時刻が[S-X,T-X)でなければならない。
また、ある時刻で複数の道路工事に遭遇しかねない場合は最寄の物を選択しなければならない。

そこで、時刻を座標圧縮したうえで区間の最小値を更新可能なSegTreeを用いると、時刻毎に最初に遭遇する道路工事の作業を求めることができる。

int N,Q;

template<class V,int NV> class SegTree_2 {
public:
	vector<V> val;
	SegTree_2(){val.resize(NV*2,1LL<<60);};
	
	V getval(int entry) {
		entry += NV;
		ll ret=val[entry];
		while(entry>1) entry>>=1, ret=min(ret,val[entry]);
		return ret;
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) val[k]=min(val[k],v);
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
		}
	}
};

SegTree_2<ll,1<<20> st;
vector<ll> C;
ll S[202020],T[202020],X[202020],D[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	C.push_back(-1LL<<60);
	C.push_back(1LL<<60);
	FOR(i,N) {
		cin>>S[i]>>T[i]>>X[i];
		C.push_back(S[i]-X[i]);
		C.push_back(T[i]-X[i]);
	}
	FOR(i,Q) {
		cin>>D[i];
		C.push_back(D[i]);
	}
	sort(ALL(C));
	C.erase(unique(ALL(C)),C.end());
	FOR(i,N) {
		x=lower_bound(ALL(C),S[i]-X[i])-C.begin();
		y=lower_bound(ALL(C),T[i]-X[i])-C.begin();
		st.update(x,y,X[i]);
	}
	
	
	FOR(i,Q) {
		x=lower_bound(ALL(C),D[i])-C.begin();
		ll ret=st.getval(x);
		if(ret>=1LL<<50) {
			cout<<-1<<endl;
		}
		else {
			cout<<ret<<endl;
		}
	}
	
	
}

まとめ

ライブラリがバグっててデバッグに30分かかった。