Submission #936679

#	Time	Username	Problem	Language	Result	Execution time	Memory
936679		Batorgil952	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	71 ms	14748 KiB

fancyfence

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair

using namespace std;

const ll N=1e5+5, mod=1e9+7;
ll h[N], w[N], tree[4*N], urt[4*N];
ll n;

void build(ll v, ll l, ll r){
	if(l==r) tree[v]=l, urt[v]=w[l];
	else{
		ll mid=(l+r)/2;
		build(2*v, l, mid);
		build(2*v+1, mid+1, r);
		if(h[tree[2*v]]<=h[tree[2*v+1]]){
			tree[v]=tree[2*v];
		}
		else{
			tree[v]=tree[2*v+1];
		}
		urt[v]=urt[2*v]+urt[2*v+1];
	}
}

ll query1(ll v, ll l, ll r, ll ql, ll qr){
	if(qr<l || r<ql) return -1;
	if(ql<=l && r<=qr) return tree[v];
	ll mid=(l+r)/2;
	ll x=query1(2*v, l, mid, ql, qr);
	ll y=query1(2*v+1, mid+1, r, ql, qr);
	if(x==-1) return y;
	if(y==-1) return x;
	if(h[x]<=h[y]) return x;
	return y;
 }

ll query2(ll v, ll l, ll r, ll ql, ll qr){
	if(qr<l || r<ql) return 0;
	if(ql<=l && r<=qr) return urt[v];
	ll mid=(l+r)/2;
	return query2(2*v, l, mid, ql, qr)+query2(2*v+1, mid+1, r, ql, qr);
}

ll Fun(ll l, ll r, ll tuvshin){
	if(l>r) return 0;
	ll p=query1(1, 1, n, l, r);
	ll q=query2(1, 1, n, l, r);
	ll a=h[p]-tuvshin;
	ll b=tuvshin;
	return ((((((q%mod)*((q+1)%mod))%mod)*500000004)%mod)*((((((2*b+a+1)%mod)*a)%mod)*500000004)%mod)%mod+Fun(l, p-1, h[p])+Fun(p+1, r, h[p]))%mod;
}

int main(){
	ll i;
	
	scanf("%lld",&n);
	
	for(i=1; i<=n; i++){
		scanf("%lld",&h[i]);
	}
	
	for(i=1; i<=n; i++){
		scanf("%lld",&w[i]);
	}
	
	build(1, 1, n);
	
	printf("%lld\n", Fun(1, n, 0));
	
	return 0;
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%lld",&n);
      |  ~~~~~^~~~~~~~~~~
fancyfence.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%lld",&h[i]);
      |   ~~~~~^~~~~~~~~~~~~~
fancyfence.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   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