Polynomial Round 2022 : F2. Magician and Pigs (Hard Version)

変な設定の問題。
https://codeforces.com/contest/1774/problem/F2

問題

以下の3種類のクエリ列を順次行う。

• HP Xの豚を1匹生成する。
• 今いる豚のHPをX減らす。
• ここまでの処理をすべて再度行う。

最終的に残る豚は何匹か。

解法

先にクエリを読んでおき、「今生まれた豚は、この後どれだけHPを減らされるか」を計算可能にしておく。
あとは、再度クエリを読み、豚生成クエリに対し、最終的にHPが正で残りそうな豚の数を数え上げよう。

int N;
const ll mo=998244353;
int S[802020],T[802020];
int num[802020];
ll TD[802020];
ll RD[802020];

ll p2[802020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<pair<ll,ll>> V,VR;
	
	p2[0]=1;
	FOR(i,801010) p2[i+1]=p2[i]*2%mo;
	
	scanf("%d",&N);
	ll CD=0;
	int TF=N+1;
	FOR(i,N) {
		scanf("%d",&S[i]);
		if(S[i]!=3) scanf("%d",&T[i]);
		if(i) TD[i]=TD[i-1];
		if(S[i]==2) {
			TD[i]+=T[i];
			CD+=T[i];
		}
		if(S[i]==3) {
			RD[i]=CD;
			if(CD<1LL<<31) {
				if(CD) TF=min(TF,(int)V.size());
				V.push_back({CD,i});
				VR.push_back({i,CD});
				CD=min(CD*2,1LL<<31);
			}
		}
		
		num[i+1]=num[i]+(S[i]==3);
	}
	if(TF==N+1) TF=V.size();
	ll ret=0;
	int ps=0;
	FOR(i,N) if(S[i]==1) {
		ll cur=T[i];
		cur-=TD[N-1]-TD[i];
		if(cur<=0) continue;
		while(ps<VR.size()&&VR[ps].first<i) ps++;
		x=ps;
		ll pat=1;
		if(TF>x) {
			pat=p2[TF-x];
			x=TF;
		}
		ll num=1;
		for(j=V.size()-1;j>=x;j--) {
			if(cur>V[j].first) {
				num+=p2[j-x];
				cur-=V[j].first;
			}
		}
		(ret+=pat*(num%mo))%=mo;
	}
	cout<<ret<<endl;
	
	
}

まとめ

結構てこずったけど、最終的に解き切れてよかった。