Submission #647115

#	Time	Username	Problem	Language	Result	Execution time	Memory
647115		jamielim	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	41 ms	6364 KiB

fancyfence

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

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n;
ll h[100005],w[100005],p[100005];
int l[100005],r[100005];

inline ll choose2(ll x){
	x%=MOD;
	return ((x)*(x-1)/2)%MOD;
}

int main(){
	//freopen("sample/input1.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&h[i]);
	for(int i=1;i<=n;i++){
		scanf("%lld",&w[i]);
		p[i]=p[i-1]+w[i];
		p[i]%=MOD;
	}
	vector<ll> stk;
	stk.pb(0);
	for(int i=1;i<=n;i++){
		while(h[stk.back()]>=h[i]){
			stk.pop_back();
		}
		l[i]=stk.back()+1;
		stk.pb(i);
	}
	stk.clear();
	stk.pb(n+1);
	for(int i=n;i>=1;i--){
		while(h[stk.back()]>h[i]){
			stk.pop_back();
		}
		r[i]=stk.back()-1;
		stk.pb(i);
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		ll cur=((p[r[i]]-p[i-1])%MOD)*((p[i]-p[l[i]-1])%MOD)-choose2(w[i])%MOD;
		cur%=MOD;
		cur*=choose2(h[i]+1);
		ans+=cur%MOD;
		ans%=MOD;
	}
	printf("%lld",(ans+MOD)%MOD);
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
fancyfence.cpp:31:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  for(int i=1;i<=n;i++)scanf("%lld",&h[i]);
      |                       ~~~~~^~~~~~~~~~~~~~
fancyfence.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%lld",&w[i]);
      |   ~~~~~^~~~~~~~~~~~~~

• 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