Submission #1308233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308233		vtnoo	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	92 ms	4636 KiB

fancyfence

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define me(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef vector<ll> vi; 
typedef pair<ll,ll> pi;
const int MOD=1e9+7,MAXN=1e5+5;
ll h[MAXN],w[MAXN],pf[MAXN];
int n;
ll mul(ll a,ll b){
	return a*b%MOD;
}
void add(ll &a,ll b){
	a+=b; a%=MOD;
}
ll exp(ll a,ll b){
	if(b==0)return 1;
	ll tmp=exp(a,b/2);
	tmp=mul(tmp,tmp);
	if(b%2)tmp=mul(tmp,a);
	return tmp;
}
ll invMul(ll a){
	return exp(a,MOD-2);
}
ll rectangle(ll a,ll b){
	return (mul(a,a+1ll)*invMul(2)%MOD)*((mul(b,b+1ll))*invMul(2)%MOD)%MOD;
}
vi small(int rev){
	stack<pi>s;
	vi ans(n,-1);
	fore(i,0,n){
		while(SZ(s)&&s.top().fst+rev>h[i]){
			s.pop();
		}
		if(SZ(s))ans[i]=s.top().snd; 
		s.push({h[i],i});
	}
	return ans;
}
ll get(int l,int r){
	if(r==-1||l==n)return 0;
	if(l==-1)return pf[r];
	return (pf[r]-pf[l]%MOD+MOD)%MOD;
}
int main(){
	cin>>n;
	fore(i,0,n)cin>>h[i];
	fore(i,0,n)cin>>w[i];
	vi l=small(0);
	reverse(h,h+n);
	vi r=small(1);
	reverse(h,h+n);
	reverse(ALL(r));
	fore(i,0,n){
		r[i]=n-r[i]-1;
	}
	fore(i,0,n){
		add(pf[i],w[i]%MOD);
		if(i)add(pf[i],pf[i-1]%MOD);
	}
	ll ans=0;
	fore(i,0,n){
		int L=l[i],R=r[i];
		//~ cout<<"=================="<<endl;
		//~ cout<<L<<" "<<R<<endl;
		ll wl=get(L,i-1),wr=get(i,R-1),wlr=0;
		//~ cout<<wl<<" "<<wr<<" ";
		add(wlr,((wl+wr)%MOD+w[i])%MOD);
		//~ cout<<wlr<<endl;
		add(ans,(rectangle(h[i],wlr)-(rectangle(h[i],wl)+rectangle(h[i],wr))%MOD+MOD)%MOD);
		//~ cout<<ans<<endl;
	}
	cout<<ans;
}		

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27