Submission #945917

#	Time	Username	Problem	Language	Result	Execution time	Memory
945917		teacup	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	67 ms	7904 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
typedef vector<int> vi;
#define iii tuple<int,int,int>
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef map<int,int> mii;

#ifndef debug
	#define cerr if (0) cerr
#endif
int N,H[100005],W[100005];
int pref[100005], last_mins[100005];
const int mod=1e9+7;
int nc2(int n){
	return ((n*(n-1))/2)%mod;
}
int rect(int h, int w){
	return (nc2(h+1)*nc2(w+1))%mod;
}
int32_t main(){
	cin>>N;
	int last_min = -1;
	for (int i=0; i<N; i++)cin>>H[i];
	for (int i=0; i<N; i++){
		cin>>W[i];
		if (i==0) pref[i]=W[i];
		else pref[i]=W[i]+pref[i-1];
		
		last_mins[i]=last_min;
		if (i>0 && H[i-1]>H[i]){
			last_min = i;
		}
	}
	
	int ans=0, sum=0;
	stack<iii> st;
	for (int i=0; i<N; i++){
		ans += rect(H[i],W[i]);
		ans %= mod;
		
		int total_w = 0;
		while (st.size() && get<0>(st.top()) >= H[i]){
			auto [h,w,p] = st.top();
			st.pop();
			total_w += w;
			total_w %= mod;
			sum = (sum-p + mod);
			sum %= mod;
		}
		ans += (sum*W[i])%mod;
		ans %= mod;
		ans += ((total_w * nc2(H[i]+1))%mod * W[i])%mod;
		ans %= mod;
		total_w += W[i];
		total_w %= mod;
		int t = total_w * nc2(H[i]+1);
		t %= mod;
		sum += t;
		sum %= mod;
		st.push({H[i], total_w, t});
	}
	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