kmjp's blog

競技プログラミング参加記です

Codeforces #390 Div2 D. Fedor and coupons

これは割と定番テクっぽいなぁ。
http://codeforces.com/contest/754/problem/D

問題

N個の1次元区間(L[i],R[i])が与えられる。
ここからK個選択し、すべての共通部分の区間の長さを最長にしたい。
そのようなK個を応えよ。

解法

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が変だったのでこれもいいのかな。