SRM 678 Div1 Medium TheEmpireStrikesBack

まず、LIS になるように余分な惑星を取り除く (x1<=x2 && y1<=y2 となっているときは、2 番目を選ぶほうが明らかに嬉しい+2 番目の惑星が取り除かれるときは、1 番目の惑星も取り除かれるので、1 番目の惑星は除外して考えて良い)
すると、T を固定したときに greedy にミサイルを打つ回数の最小値が求められるようになるので、二分探索する。

class TheEmpireStrikesBack {
	public:
	int find(int AX, int BX, int CX, int AY, int BY, int CY, int N, int M) {
		set<P> st;
		P p = P(AX, AY);
		st.insert(p);
		rep(i, N-1){
			p = P((p.fst*BX+CX)%mod, (p.snd*BY+CY)%mod);
			st.insert(p);
		}
		for(auto it = st.begin(); it!=st.end();){
			auto it2 = it;
			++it2;
			if(it2==st.end()) break;
			if(it->snd<=it2->snd){
				st.erase(it);
				it = it2;
				if(it!=st.begin()) --it;
			} else ++it;
		}
		vector<ll> x, y;
		for(auto &&val: st){
			x.pb(val.fst);
			y.pb(-val.snd);
		}
		int n = x.size();

		ll lb = -1, ub = 1e9;
		while(ub-lb>1){
			ll md = (lb+ub+1)/2;
			int m = 0;
			int pos = 0;
			while(pos<n){
				int pos2 =upper_bound(all(y), y[pos]+md)-y.begin()-1;
				pos = upper_bound(all(x), x[pos2]+md)-x.begin();
				m++;
			}
			(m<=M?ub:lb)=md;
		}
		return ub;
	}
};