Submission #302361

#	Time	Username	Problem	Language	Result	Execution time	Memory
302361		errorgorn	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	30 ms	4608 KiB

fancyfence

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int MOD=1000000007;

ll fix(ll i){
	i%=MOD;
	if (i<0) i+=MOD;
	return i;
}

ll nC2(ll i){
	return i*(i+1)/2%MOD;
}

ll calc(ll lo,ll hi,ll len){
	//cout<<lo<<" "<<hi<<" "<<len<<endl;
	return nC2(len)*(nC2(hi)-nC2(lo))%MOD;
}

int n;
ll h[100005];
ll w[100005];
vector<int> stk;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	rep(x,1,n+1) cin>>h[x];
	rep(x,1,n+1){
		cin>>w[x];
		w[x]=(w[x-1]+w[x])%MOD;
	}
	
	stk.push_back(0);
	
	ll ans=0;
	rep(x,1,n+1){
		while (h[stk.back()]>h[x]){
			int temp=h[stk.back()];
			stk.pop_back();
			ans+=calc(max(h[stk.back()],h[x]),temp,fix(w[x-1]-w[stk.back()]));
		}
		stk.push_back(x);
	}
	
	while (sz(stk)>1){
		int temp=h[stk.back()];
		stk.pop_back();
		ans+=calc(h[stk.back()],temp,fix(w[n]-w[stk.back()]));
	}
	
	cout<<fix(ans)<<endl;
}

• 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