Submission #647027

#	Time	Username	Problem	Language	Result	Execution time	Memory
647027		jamielim	Fancy Fence (CEOI20_fancyfence)	C++14	55 / 100	32 ms	3520 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;
int h[100005],w[100005];

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

int main(){
	//freopen("sample/input1.txt","r",stdin);
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&h[i]);
	for(int i=0;i<n;i++)scanf("%d",&w[i]);
	ll ans=0;
	vector<pair<ll,ll> > stk;
	stk.pb(0,0);
	ll cur=0;
	for(int i=0;i<n;i++){
		ll sum=0;
		while(stk.back().fi>h[i]){
			ii p=stk.back();stk.pop_back();
			cur-=((p.se%MOD)*choose2(p.fi+1))%MOD;
			cur%=MOD;
			sum+=p.se;
		}
		cur+=((sum%MOD)*choose2(h[i]+1))%MOD;
		cur%=MOD;cur+=MOD;cur%=MOD;
		
		ans+=(cur*(ll)(w[i]))%MOD; // left side is strictly from previous block, right side is (,] of current block
		ans%=MOD;
		//printf("a' %lld\n",ans);
		
		ans+=((choose2(h[i]+1)%MOD)*(choose2(w[i]+1)%MOD))%MOD; // left side is within current block
		ans%=MOD;
		//printf("a %lld\n",ans);
		
		cur+=((w[i]%MOD)*choose2(h[i]+1))%MOD;
		stk.pb(h[i],sum+w[i]);
	}
	printf("%lld",((ans%MOD)+MOD)%MOD);
}

Compilation message (stderr)

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

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27