Submission #1298577

#TimeUsernameProblemLanguageResultExecution timeMemory
1298577PieArmyFancy Fence (CEOI20_fancyfence)C++20
100 / 100
18 ms2180 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

const int mod=1e9+7;

int sum(int x,int y){
	if(x+y<mod)return x+y;
	return x+y-mod;
}

int sub(int x,int y){
	if(y)y=mod-y;
	return sum(x,y);
}

int mul(ll x,ll y){
	return x*y%mod;
}

int cal(int x){
	return mul(mul(x,sum(x,1)),500000004);
}

int n;
int h[100023],w[100023];
int ans=0;

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	vector<pair<int,int>>sta;
	int val=0;
	for(int i=1;i<=n;i++){
		int x=0;
		while(sta.size()&&sta.back().fr>=h[i]){
			val=sub(val,mul(sta.back().sc,cal(sta.back().fr)));
			x=sum(x,sta.back().sc);
			sta.pop_back();
		}
		if(x){
			sta.pb({h[i],x});
			val=sum(val,mul(x,cal(h[i])));
		}
		ans=sum(ans,mul(val,w[i]));
		ans=sum(ans,mul(cal(w[i]),cal(h[i])));
		x=w[i];
		while(sta.size()&&sta.back().fr>=h[i]){
			val=sub(val,mul(sta.back().sc,cal(sta.back().fr)));
			x=sum(x,sta.back().sc);
			sta.pop_back();
		}
		if(x){
			sta.pb({h[i],x});
			val=sum(val,mul(x,cal(h[i])));
		}
	}
	cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...