oj.uz

Submission #412896

# Submission time Handle Problem Language Result Execution time Memory
412896 2021-05-27T18:41:38 Z Pbezz Fancy Fence (CEOI20_fancyfence) C++14
13 / 100
 27 ms 3792 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define pb push_back
#define mp make_pair
typedef pair<ll,ll> pii;
 
typedef tree<ll ,null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
const ll MAXN = 450;
const ll MOD = 1e9+7;
const ll INF = 1e9+10;
 
ll calc(ll n, ll m){
m%=MOD; n%=MOD;

ll res = (n*(n+1))%MOD;
if(res%2==1)res+=MOD;
res/=2;
res%=MOD;

ll k = (m*(m+1))%MOD;
if(k%2==1)k+=MOD;
k/=2;
k%=MOD;

res*=k;
res%=MOD;
if(res<0)res+=MOD;

return res;
}



int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	ll n,i,k,ans=0,maxi=0,mini=INF,sum=0;
	cin>>n;

	ll h[n+2],w[n+2],dp[n+1]; dp[0]=0;
	for(i=1;i<=n;i++){
	cin>>h[i];
	maxi = max(maxi,h[i]);
	mini = min(mini,h[i]);
	}
	for(i=1;i<=n;i++){
	cin>>w[i];
	sum+=w[i];
	dp[i] = dp[i-1]+w[i];
	}

	if(maxi==mini){//subtask 4

	ans = calc(h[0],sum);

}else if(maxi<=2){//subtask 3

	for(i=1;i<n;i++){
	if(h[i]==h[i+1]){
	w[i+1]+=w[i];
	w[i]=0;
	}
	}

	for(i=1;i<=n;i++){
	if(w[i]==0)continue;

	ans += calc(h[i],w[i]);
	ans -= calc(1,w[i]);
	ans%=MOD;
	}

	ans += calc(1,sum);
	ans%=MOD;
}else{

	stack <ll>st;
	ll left[n+1],right[n+1];
	bool meh[n+1];

	for(i=1;i<=n;i++){
	meh[i]=true;
	while(!st.empty()&&h[st.top()]>=h[i]){
	if(h[st.top()]==h[i])meh[i]=false;

	st.pop();
	}

	if(!st.empty()){
	left[i]=st.top();
	}else{
	left[i]=0;
	}
	st.push(i);
//cout<<left[i]<<" ";
}//cout<<endl;
while(!st.empty())st.pop();

	for(i=n;i>=1;i--){
	while(!st.empty()&&h[st.top()]>=h[i]){
	st.pop();
	}

	if(!st.empty()){
	right[i]=st.top();
	}else{
	right[i]=n+1;
	}
	st.push(i);
}

	h[n+1]=0;
	for(i=1;i<=n;i++){

	if(meh[i]==false)continue;

	//k = right[i]-left[i]-1;//k é a soma no intervalo
	k = dp[right[i]-1] - dp[left[i]];
	ans += calc(k,h[i]);
	ans -= calc(k , max(h[left[i]], h[right[i]]) );
	//cout<<i<<" "<<k<<" "<<h[i]<<endl;
}



/*
6
1 2 3 2 2 1
1 1 1 1 1 1
*/






}
	if(ans<0)ans+=MOD;
	cout<<ans<<endl;
return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 12 ms 1996 KB Output is correct
4 Correct 27 ms 3784 KB Output is correct
5 Correct 24 ms 3792 KB Output is correct
6 Correct 24 ms 3792 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 2 ms 328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct