HackerRank HourRank 26 : B. Cloudy Day

今回はいい感じに解けて良かった。
https://www.hackerrank.com/contests/hourrank-26/challenges

問題

N個の町が一直線上に並んでおり、その位置と人口が与えられる。
ここでM個の雲がある。各雲はある区間を覆っている。

1個の雲を消すことができるとき、雲に覆われない町の総人口を最大化せよ。

解法

累積和の要領で、各町がいくつの雲に覆われているかを求めよう。
雲が1個も覆われてない町はどのみち答えに含まれるので先に数え上げておこう。

後は、雲1個だけに覆われている町に関し、BITなり累積和なりで区間和を求められる状況にしておく。
そうすると、雲を1つ消した際にその雲が相当する区間和の部分だけ新たに雲に覆われずにいる人が増えるので、その最大値を求めれば解となる。

int N,M;
pair<int,int> P[202020];
int L[202020],R[202020];

int X[202020],C[202020];
int cnt[202020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i].second;
	FOR(i,N) cin>>P[i].first;
	sort(P,P+N);
	FOR(i,N) {
		X[i]=P[i].first;
		C[i]=P[i].second;
	}
	cin>>M;
	FOR(i,M) cin>>L[i];
	FOR(i,M) cin>>R[i];
	FOR(i,M) {
		x=L[i];
		y=R[i];
		L[i]=lower_bound(X,X+N,x-y)-X;
		R[i]=lower_bound(X,X+N,x+y+1)-X;
		cnt[L[i]]++;
		cnt[R[i]]--;
	}
	ll S=0;
	FOR(i,N) {
		if(i) cnt[i]+=cnt[i-1];
		if(cnt[i]==0) S+=C[i];
		if(cnt[i]==1) bt.add(i,C[i]);
	}
	ll ma=S;
	FOR(i,M) {
		ll cnt=S+(bt(R[i]-1)-bt(L[i]-1));
		ma=max(ma,cnt);
	}
	cout<<ma<<endl;
}

まとめ

これは30点台でもよさそうな問題。