Submission #42181933

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const ll MAXN = 2e5+10,INF=1e18;
void tomin(ll& x,ll y){x=min(x,y);}
void tomax(ll& x,ll y){x=max(x,y);}

ll n,x;
ll a[MAXN],b[MAXN],pre[MAXN];
ll to[MAXN][30]; //向后跳x次

int tmp[MAXN],tot;
ll S[MAXN];

int cmp(int x,int y){
	assert(a[x] > 1);assert(a[y] > 1);
	return b[x] * (a[y]-1) < b[y] * (a[x]-1);
}

typedef array<ll,2> pr;

void chk(pr& x,pr y,int md){
	if(x[0] > y[0])x=y;
	else if((x[0]==y[0])){
		if(!md){
			if(x[1] < y[1])x=y;
		}else{
			if(x[1] > y[1])x=y;
		}
	}
}
pr operator+(pr x,pr y){
	return {x[0]+y[0],x[1]+y[1]};
}
//

pr dp[MAXN];

pr p[MAXN],g[MAXN];

pr chk(ll mid,int md=0){
	rep(i,0,n)dp[i] = g[i] = p[i] = {INF,INF};
	dp[0] = {0,0};

	rep(i,1,n){
		p[i-1] = dp[i-1] + (pr){-S[i-1],0};
		if(i>1)chk(p[i-1],p[i-2],md);

		if(a[i] > 1){
			g[i] = p[i-1];
			p[i-1] = {INF,INF};
		}else{
			pr v = p[i-1] + (pr){S[i]-mid,1};
			chk(dp[i],v,md);
		}

		int u=pre[i],j=1;
		while(u){
			if(j==30)break;
			pr v = g[u] + (pr){S[i]-mid + to[i][j],1};
			chk(dp[i],v,md);

			u=pre[u-1];j++;
		}
	}

	return dp[n];
}

int main(){

	ios::sync_with_stdio(false);

	cin>>n>>x;
	rep(i,1,n){
		cin>>a[i]>>b[i];
		pre[i] = (a[i]!=1) ? (i) : (pre[i-1]);
		S[i] = S[i-1] + ((a[i]==1) ? (b[i]) : (0));
	}


	rep(i,1,n){
		int u=i;tot=0;
		rep(j,1,29){
			if(!pre[u])break;
			u=pre[u];
			tmp[++tot]=u;
			sort(tmp+1,tmp+1+tot,cmp);

			ll S=0;
			rep(k,1,tot){
				S=S*a[tmp[k]]+b[tmp[k]];
				if(S>x){S=INF;break;}
			}
			to[i][j]=S;
			u--;
		}
	}

	
	ll L=-1e9,R=0,ret=INF;

	while(L<=R){
		ll mid=(L+R)/2;
		pr tmp=chk(mid);
		ll val=tmp[0] + tmp[1]*mid;
		if(val <= x){
			ret=mid;R=mid-1;
		}else{
			L=mid+1;
		}
	}
	
	assert(ret!=INF);
	
	pr Rv=chk(ret),Lv=chk(ret,1); 

	ll val = Rv[0] + Rv[1] * ret;
	
	assert(val <= x);
	ll diff = min(Rv[1] - Lv[1],(x-val) / (-ret) );

	cout<<Rv[1] - diff<<" "<<val-diff*ret<<" ";

    return 0;
}

Submission Info

Judge Result