VK Cup 2015 Round 3 : A. Place Your Ad Here

忘れないうちに。
http://codeforces.com/contest/542/problem/A

問題

N本のCMとM個のTV放送枠がある。
各CMは、時間帯[L[i],R[i]]に放送可能である。
各放送枠は、同じく時間帯[A[j],B[j]]に放送可能であり、その視聴者数はC[j]である。

ここで1つのCMを1つの放送枠で流したい。(CMは一部分だけ流しても良い。)

CMを流したときの効果は、流した時間帯とその視聴者の積である。
最適な放送をした場合、得られる効果の最大値を求めよ。

解法

時間順にCMの開始・終了及び放送枠の開始・終了をsweepしていく。
そのため、各開始終了イベントを時刻順にソートしていく。

以後、処理中の時刻で放送可能なCMを開始時刻順及び終了時刻順でソートしたsetを持っておく。
これを使ってTV放送時間開始または終了を跨ぐCMを処理していく。

また、TV放送時間内に開始かつ終了したCMを処理するため、終了済みのCMの最大長を管理できるように、時間を座標圧縮したうえで、開始時刻に対応する最長放送時間を返すSegTreeを作ろう。
以下時間毎に以下のように処理していく。

• 放送が開始したとき：その時点で放送可能なCMのうち、終了時刻が一番遅いものを選択、効果の最大値を求める。
• 放送が終了したとき
  • その時点で放送可能なCMのうち、開始時刻が一番遅いものを選択、効果の最大値を求める。
  • 上記SegTreeを使い、放送時間内に開始かつ終了したCMの最長時間を求め、効果の最大値を求める。
• CMの開始終了はSegTreeやsetの更新を行う。

int N,M;
int L[202020],R[202020];
int A[202020],B[202020],C[202020];
ll ret;
int idx,idy;

set<pair<int,int> > Ls,Rs;
vector<pair<int,int> > events;
vector<int> P;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

SegTree_1<ll,1<<20> ST;
map<int,int> MM;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>L[i]>>R[i];
		if(L[i]<R[i]) {
			events.push_back({L[i],i+300000});
			events.push_back({R[i],i+300000});
		}
		P.push_back(L[i]);
	}
	FOR(i,M) {
		cin>>A[i]>>B[i]>>C[i];
		if(A[i]<B[i]) {
			events.push_back({A[i],i});
			events.push_back({B[i],i});
		}
		P.push_back(A[i]);
		P.push_back(B[i]);
	}
	sort(ALL(events));
	sort(ALL(P));
	P.erase(unique(ALL(P)),P.end());
	
	FORR(e,events) {
		int pos=e.first;
		r = e.second;
		if(r<300000) {
			if(A[r]==pos) {
				if(Rs.size()) {
					ll len = min(B[r],Rs.rbegin()->first)-pos;
					if(ret<len*C[r]) {
						ret=len*C[r];
						idx=Rs.rbegin()->second;
						idy=r;
					}
				}
			}
			else if(B[r]==pos) {
				if(Ls.size()) {
					ll len = pos-max(A[r],Ls.begin()->first);
					if(ret<len*C[r]) {
						ret=len*C[r];
						idx=Ls.begin()->second;
						idy=r;
					}
				}
				x = lower_bound(ALL(P),A[r])-P.begin();
				y = lower_bound(ALL(P),B[r])-P.begin();
				ll len = ST.getval(x,y);
				if(ret<len*C[r]) {
					ret=len*C[r];
					idx=MM[len];
					idy=r;
				}
			}
		}
		else {
			r-=300000;
			if(L[r]==pos) {
				if(Rs.empty() || Rs.rbegin()->first<R[r]) {
					Ls.insert({L[r],r});
					Rs.insert({R[r],r});
				}
			}
			else {
				if(Rs.count({R[r],r})) {
					l = lower_bound(ALL(P),L[r])-P.begin();
					ST.update(l,R[r]-L[r]);
					MM[R[r]-L[r]]=r;
					
					Ls.erase({L[r],r});
					Rs.erase({R[r],r});
				}
			}
		}
	}
	
	if(ret) {
		cout<<ret<<endl;
		cout<<(idx+1)<<" "<<(idy+1)<<endl;
	}
	else {
		cout<<0<<endl;
	}
	
}

まとめ

Codeforcesらしい問題。