Submission #1219034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219034		nguyenletrung	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	72 ms	8404 KiB

fancyfence

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
ll const mod=1e9+7;
int n,h[100005],w[100005];
ll tw[400005],ans;
pair<int,int> th[400005];

void build(int id,int l,int r)
{
	if(l==r)
	{
		th[id]={h[l],l};
		tw[id]=w[l];
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	tw[id]=tw[id*2]+tw[id*2+1];
	tw[id]%=mod;
	th[id]=min(th[id*2],th[id*2+1]);
}

pair<int,int> geth(int id,int l,int r,int u,int v)
{
	if(r<u||v<l) return {1e9+9,1e9+9};
	if(u<=l&&r<=v)
	{
		return th[id];
	}
	int mid=(l+r)/2;
	return min(geth(id*2,l,mid,u,v),geth(id*2+1,mid+1,r,u,v));
}

ll getw(int id,int l,int r,int u,int v)
{
	if(r<u||v<l) return 0;
	if(u<=l&&r<=v)
	{
		return tw[id];
	}
	int mid=(l+r)/2;
	return (getw(id*2,l,mid,u,v)+getw(id*2+1,mid+1,r,u,v))%mod;
}

ll get(ll x,ll y)
{
	return (x*(x+1)/2%mod)%mod*(y*(y+1)/2%mod)%mod;
}

void solve(int l,int r)
{
	if(r<l) return;
	pair<int,int> p=geth(1,1,n,l,r);
	ll hh=p.fi,id=p.se;
	
	ll a=getw(1,1,n,l,id-1),b=w[id],c=getw(1,1,n,id+1,r);
	ll sum=a+b+c;
	
	ll val=(( get(hh,sum) - get(hh,a) - get(hh,c)  )%mod+mod)%mod;
	
	
	ans+=val;
	ans%=mod;
	solve(l,id-1);
	solve(id+1,r);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//	freopen(".inp","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin>>w[i];
	}
	
	build(1,1,n);
	
	solve(1,n);
	
	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