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; } };