Submission #945685

#	Time	Username	Problem	Language	Result	Execution time	Memory
945685		WongYiKai	Fancy Fence (CEOI20_fancyfence)	C++14	30 / 100	20 ms	4444 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	ll m = 1000000007;
	cin >> n;
	ll h[n+5],w[n+5];
	ll prefw[n+5];
	ll w2 = 0;
	for (int i=0;i<n;i++){
		ll temp;
		cin >> temp;
		h[i] = temp;
	}
	for (int i=0;i<n;i++){
		ll temp;
		cin >> temp;
		w[i] = temp;
		w2 += temp;
		w2%=m;
		prefw[i] = w2;
	}
	stack<pair<ll,ll>> s;
	ll total=0;
	for (int i=0;i<n;i++){
		ll num=0;
		ll carry=0;
		while (!s.empty() && h[s.top().first]>h[i]){
			s.pop();
		}
		if (!s.empty()){
			carry += s.top().second;
			carry%=m;
			//cout << carry << " ";
			ll height = h[i]-h[s.top().first];
			ll width = prefw[i]-prefw[s.top().first]-w[i];
			height = height*(height+1)/2;
			height%=m;
			carry += (height*width)%m;
			carry%=m;
		}
		else{
			ll height = h[i];
			ll width = prefw[i]-w[i];
			height = height*(height+1)/2;
			height%=m;
			carry += (height*width)%m;
			carry%=m;
		}
		//cout << carry << " ";
		ll height = h[i];
		ll width = w[i];
		num += (carry*width)%m;
		num%=m;
		height = height*(height+1)/2;
		ll w2 = width*(width+1)/2;
		height%=m;
		w2%=m;
		num += (height*w2)%m;
		num%=m;
		carry += (height*width)%m;
		carry%=m;
		s.push({i,carry});
		total += num;
		total %=m;
	}
	cout << total%m;
}
		

• 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