Submission #1288992

#TimeUsernameProblemLanguageResultExecution timeMemory
1288992WH8Fancy Fence (CEOI20_fancyfence)C++20
100 / 100
68 ms5164 KiB
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>
int ans=0;
const int mod=1e9+7;
signed main(){
	int n;cin>>n;
	vector<int> h(n+1, 0), w(n+1, 0);
	for(int i=1;i<=n;i++)cin>>h[i];
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=n;i++){
		ans=(ans+(h[i]*h[i]+h[i])/2%mod * ((w[i]*w[i]+w[i])/2%mod))%mod;
	}
	vector<tuple<int,int,int>> v;
	for(int i=1;i<=n;i++){
		int sm=0;
		while(!v.empty() and get<0>(v.back()) >= h[i]){
			sm=(sm+get<1>(v.back()))%mod;
			v.pop_back();
		}
		int rem=(v.empty() ? 0 : get<2>(v.back()));
		int pop=sm*((h[i]*h[i]+h[i])/2%mod)%mod;
		
		ans=(ans+(rem+pop)%mod*w[i]%mod)%mod;
		sm=(sm+w[i])%mod;
		int topans=(rem+sm*((h[i]*h[i]+h[i])/2%mod)%mod)%mod;  
		v.push_back({h[i], sm, topans});
		//~ printf("i %lld, ans %lld, rem %lld, pop %lld\n", i, ans, rem ,pop);
	}
	cout<<ans%mod;
}
#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...