Codeforces #996 : Div2 E. Haystacks

Haystackというと昔読んだ論文名を思い出すんだよな…。
https://codeforces.com/contest/2055/problem/E

問題

N個の干し草の山があり、それぞれ初期状態で山の高さはA[i]である。
干し草を他の山に移すことで、各山をそれぞれ1回以上空にしたい。
ただし、一旦空にした山にまた干し草を積む時、高さの合計はB[i]以下でなければならない。

干し草を動かす総量を答えよ。

解法

先に干し草を空にする順を定めたとする。
i番目の山を空にするとき、1～(i-1)番目の山にまだ積めるならそちらに動かすのが良い。
ダメならいったんN番目の山に積もう。
こうすることで、各干し草の移動回数は1回か2回に収まる。

この際、干し草を空にする順番は以下が良い。

• A[i]＜B[i]な山を、A[i]の昇順に空にする
• A[i]=B[i]な山は、任意の順で良い
• A[i]＞B[i]な山は、B[i]の降順に空にする

int T;
int N;
ll A[505050],B[505050];
int order[505050];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	V comp(V l,V r){
		V m;
		m.first=l.first+r.first;
		m.second=max(l.second,l.first+r.second);
		return m;
	};
	
	SegTree_1(){val=vector<V>(NV*2,{0,-1LL<<60});};
	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<pair<ll,ll>,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		vector<pair<int,int>> X,Y,Z;
		ll SA=0,SB=0;
		FOR(i,N) {
			cin>>A[i]>>B[i];
			
			if(A[i]<B[i]) X.push_back({A[i],i});
			if(A[i]==B[i]) Y.push_back({i,i});
			if(A[i]>B[i]) Z.push_back({-B[i],i});
			SA+=A[i];
			SB+=B[i];
		}
		sort(ALL(X));
		sort(ALL(Y));
		sort(ALL(Z));
		FOR(i,X.size()) order[i]=X[i].second;
		FOR(i,Y.size()) order[i+X.size()]=Y[i].second;
		FOR(i,Z.size()) order[i+X.size()+Y.size()]=Z[i].second;
		A[N]=B[N]=0;
		
		FOR(i,N+1) {
			st.update(i,{A[order[i]]-B[order[i]],A[order[i]]});
		}
		ll ret=1LL<<60;
		FOR(i,N) {
			if(SA<=SB-B[order[i]]) {
				st.update(N,{A[order[i]]-B[order[i]],A[order[i]]});
				st.update(i,{0,0});
				ret=min(ret,st.val[1].second);
				st.update(i,{A[order[i]]-B[order[i]],A[order[i]]});
				st.update(N,{0,0});
			}
		}
		
		if(ret==1LL<<60) {
			cout<<-1<<endl;
		}
		else {
			cout<<ret+SA<<endl;
		}
		
		FOR(i,N+1) {
			st.update(i,{0,-1LL<<60});
		}
		
	}
}

まとめ

こういうのOI系の印象あるな…。