Submission #577521

#	Time	Username	Problem	Language	Result	Execution time	Memory
577521		amunduzbaev	Fancy Fence (CEOI20_fancyfence)	C++17	30 / 100	28 ms	5152 KiB

fancyfence

#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 inv = 5e8 + 4;
	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 T = (pref[r[i] - 1] - pref[l[i]]) % mod;
		int tot = (T * 1ll * (T + 1) % mod - L * 1ll * (L + 1) % mod - R * 1ll * (R + 1) % mod + mod + mod) % mod;
		tot = tot * 1ll * inv % mod;
		//~ T = (w[i] * 1ll * (w[i] + 1) / 2 % mod + L * 1ll * R % mod + w[i] * 1ll * (L + R) % mod) % mod;
		//~ cout<<T<<" "<<tot<<"\n";
		T = h[i] * 1ll * (h[i] + 1) / 2 % mod;
		res = (res + tot * 1ll * T) % mod;
	}
	
	cout<<res<<"\n";
}

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