これは割と定番テクっぽいなぁ。
http://codeforces.com/contest/754/problem/D
解法
R[i]の上位K個を持つような集合Sを管理しながら、区間をL[i]昇順に処理していく。
区間(L[i],R[i])を処理する際、SにR[i]を追加する。
その際SがK要素を超えるようであればSのうちR[x]が最小のxを取り除く。
すると(L[i],(Sの最小値))がL[i]を左端とするK要素の共通部分の長さとなる。
上記値の最大値を答えればよい。
int N,K; ll L[303030],R[303030]; map<int,vector<int>> E; int ma=0; int id=-1; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; FOR(i,N) { cin>>L[i]>>R[i]; E[L[i]].push_back(i); E[R[i]].push_back(i+1000000); } set<pair<int,int>> S; FORR(r,E) { sort(ALL(r.second)); FORR(e,r.second) { if(e<1000000) { S.insert({R[e],e}); if(S.size()>K) S.erase(S.begin()); if(S.size()==K) { ll d=S.begin()->first-r.first+1; if(d>ma) { ma=d; id=e; } } } else { S.erase({R[e-1000000],e-1000000}); } } } if(id==-1) { _P("0\n"); FOR(i,K) _P("%d%c",i+1,(i==K-1)?'\n':' '); } S.clear(); FORR(r,E) { sort(ALL(r.second)); FORR(e,r.second) { if(e<1000000) { S.insert({R[e],e}); if(S.size()>K) S.erase(S.begin()); if(e==id) { _P("%d\n",ma); FORR(r,S) _P("%d ",r.second+1); _P("\n"); return; } } else { S.erase({R[e-1000000],e-1000000}); } } } }
まとめ
えらくオーソドックスな問題だけど、C,Eが変だったのでこれもいいのかな。