제출 #577514

#제출 시각아이디문제언어결과실행 시간메모리
577514amunduzbaevFancy Fence (CEOI20_fancyfence)C++17
30 / 100
28 ms7176 KiB
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int h[N], w[N], pref[N];
int l[N], r[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
		pref[i] = pref[i-1] + w[i];
	}
	
	vector<int> ss;
	for(int i=1;i<=n;i++){
		while(!ss.empty() && h[ss.back()] > h[i]){
			ss.pop_back();
		}
		
		if(!ss.empty()) l[i] = ss.back();
		else l[i] = 0;
		ss.push_back(i);
	}
	
	ss.clear();
	for(int i=n;i>0;i--){
		while(!ss.empty() && h[ss.back()] >= h[i]){
			ss.pop_back();
		}
		
		if(!ss.empty()) r[i] = ss.back();
		else r[i] = n + 1;
	}
	
	int res = 0;
	for(int i=1;i<=n;i++){
		int L = (pref[i-1] - pref[l[i]]) % mod, R = (pref[r[i]-1] - pref[i]) % mod;
		int tot = (w[i] * 1ll * (w[i] + 1) / 2 % mod + L * 1ll * R % mod + w[i] * 1ll * (L + R) % mod) % mod;
		res = (res + tot * 1ll * (h[i] * 1ll * (h[i] + 1) / 2 % mod)) % mod;
	}
	
	cout<<res<<"\n";
}
#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...