Codeforces #322 Div2 E. Kojiro and Furrari

EよりFの方がだいぶ簡単。
http://codeforces.com/contest/581/problem/E

問題

一直線の道路があり、ゴールは座標Eにある。
今車で座標F[i]からEに向かいたい。

車は最大Sの容積のガソリンを積むことができる。車は1進むとガソリンを1消費する。
ガソリンには優良可の３段階のグレードがあり、初期状態では車は優のガソリンを満タンに積んでいる。

道路中、N箇所のガソリンスタンドがあり、それぞれで買えるガソリンの質T[i]と位置X[i]がわかっている。
車はどのガソリンでも走るし、タンクに（合計がS以下で有れば）混ざっていても構わない。
ただ、できるだけ良質のガソリンで走りたい。

M個のクエリとして初期位置F[i]が与えられる。
各初期位置からゴールに向かう際、途中で補給しなければならない可・良のガソリンの量の最小値を求めよ。
可のガソリン補給量が同じ複数の補給方法があるなら、良のガソリンが最小のものを答えよ。

解法

ゴールから近い順にガソリンスタンドを処理していき、
「ゴールに到達するために、ここでどれだけのガソリンまで補給しなければならないか、またここでの補給如何にかかわらず、次の補給ガソリンスタンド以降で必要な可・良のガソリン量」
を順次処理していく。
また、その過程で同様にゴールから近い順にクエリを処理していく。
各初期位置クエリの処理は、優のガソリン満タンでスタートできる点で、優のガソリンスタンドと同様な処理で良い（ただしガソリンスタンドと異なり、以降の処理で補給対象とならない）

各ガソリンスタンドの処理では以下のように処理していく。

• ここからゴールに向けて距離S以内に、今いるガソリンスタンドと同質またはより良いガソリンスタンドがあるなら、そこに行く分だけここで補給すればよい。
• 上記ガソリンスタンドはないが、ゴールに向けて距離S以内に質の悪いガソリンスタンドならある場合、このガソリンスタンドで満タンにしてそこまで行く。
  • 次のガソリンスタンドにガソリンを残していければ、そこで補給する質の悪いガソリンの量を減らすことができる。

上記処理では最寄のガソリンスタンドと、S以内で最遠のガソリンスタンドの位置を高速に求める必要がある。
lower_bound等二分探索でも良いし、尺取法でも良い。
ただ、以下は尺取法だが1s以上かかっている。

int E,S,N,M;
set<int> POS;
map<int,int> G;
map<int,vector<int> > C;
map<int,pair<ll,ll> > gas;
map<int,ll > need;
pair<ll,ll> ret[202000];
vector<int> P[4];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>E>>S>>N>>M;
	FOR(i,N) {
		cin>>r>>x;
		if(x>=E) continue;
		G[E-x] = max(G[E-x],r);
		POS.insert(E-x);
	}
	
	G[0]=3;
	P[1].push_back(0);
	P[2].push_back(0);
	FORR(r,G) P[r.second].push_back(r.first);
	gas[0]={0,0};
	need[0]=0;
	
	FOR(i,M) {
		cin>>x;
		C[E-x].push_back(i);
		POS.insert(E-x);
	}
	
	vector<int>::iterator pre[4],last[4];
	for(i=1;i<=3;i++) pre[i]=last[i]=P[i].begin();
	
	FORR(r,POS) {
		for(i=1;i<=3;i++) while(pre[i]!=P[i].end() && r-*pre[i]>S) pre[i]++;
		
		int t = G[r];
		if(t) {
			gas[r]={1LL<<40,1LL<<40};
			
			if(t==3) {
				need[r]=0;
				if(last[3]!=P[3].end() && r-*last[3]<=S) {
					gas[r] = gas[*last[3]];
				}
				else if(pre[2]!=P[2].end() && *pre[2]<r) {
					int left=S-(r-*pre[2]);
					gas[r] = {gas[*pre[2]].first,gas[*pre[2]].second + max(0LL,need[*pre[2]]-left)};
				}
				else if(pre[1]!=P[1].end() && *pre[1]<r) {
					int left=S-(r-*pre[1]);
					gas[r] = {gas[*pre[1]].first + max(0LL,need[*pre[1]]-left) ,gas[*pre[1]].second };
				}
			}
			else if(t==2) {
				if(last[3]!=P[3].end() && r-*last[3]<=S) {
					gas[r] = gas[*last[3]];
					need[r]= r-*last[3];
				}
				else if(last[2]!=P[2].end() && r-*last[2]<=S) {
					gas[r] = gas[*last[2]];
					gas[r].second += need[*last[2]];
					need[r]= r-*last[2];
				}
				else if(pre[1]!=P[1].end() && *pre[1]<r) {
					int left=S-(r-*pre[1]);
					gas[r] = {gas[*pre[1]].first + max(0LL,need[*pre[1]]-left) ,gas[*pre[1]].second };
					need[r]= S;
				}
			}
			else if(t==1) {
				int mi=4;
				for(i=3;i>=1;i--) if(last[i]!=P[i].end() && (mi==4 || *last[i]>*last[mi]) && r-*last[i]<=S) mi=i;
				if(mi!=4) {
					gas[r] = gas[*last[mi]];
					if(mi==1) gas[r].first += need[*last[mi]];
					if(mi==2) gas[r].second += need[*last[mi]];
					need[r]= r-*last[mi];
				}
				
			}
			last[t]++;
		}
		
		if(C.count(r)) {
			pair<ll,ll> tret={1LL<<40,1LL<<40};
			if(last[3]!=P[3].end() && r-*last[3]<=S) {
				tret = gas[*last[3]];
			}
			else if(pre[2]!=P[2].end() && *pre[2]<r) {
				int left=S-(r-*pre[2]);
				tret = {gas[*pre[2]].first,gas[*pre[2]].second + max(0LL,need[*pre[2]]-left)};
			}
			else if(pre[1]!=P[1].end() && *pre[1]<r) {
				int left=S-(r-*pre[1]);
				tret = {gas[*pre[1]].first + max(0LL,need[*pre[1]]-left) ,gas[*pre[1]].second };
			}
			if(tret.first>=1LL<<40) tret.first=tret.second=-1;
			FORR(r2,C[r]) ret[r2]=tret;
		}
	}
	
	FOR(i,M) _P("%d %d\n",(int)ret[i].first,(int)ret[i].second);
}

まとめ

すごいテクを使うわけじゃないけど、場合分けが面倒。