Submission #851296

#	Time	Username	Problem	Language	Result	Execution time	Memory
851296		Jawad_Akbar_JJ	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	255 ms	31720 KiB

fancyfence

#include <bits/stdc++.h>
 
using namespace std;
#define int long long
const int N = 1<<17;
int r[N][3];
int w[N];
int h[N];
int pre[N];
int ans = 0;
int mod = 1e9 + 7;

struct node{
	int l,r;
	node* left;
	node* right;
	int ind;
	bool lft,rgt;

	node(int ll,int rr){
		l = ll;
		r = rr;
		left = right = NULL;
		lft = rgt = false;
		ind = 0;
	}

	void insert(int i){
		if(i<l or i>=r)
			return;
		if (r-l==1){
			ind = i;
			return; 
		}
		if (!lft)
			left = new node(l,(l+r)/2);
		if (!rgt)
			right = new node((l+r)/2,r);
		lft = rgt = true;
		left->insert(i);
		right->insert(i);
		if (h[left->ind]<h[right->ind])
			ind = left->ind;
		else
			ind = right->ind;
	}

	int get(int ll,int rr){
		// if (ll==rr)
		// 	cout<<ll<<" "<<rr<<endl;
		ll = max(ll,l);
		rr = min(rr,r);
		if (ll>=r or rr<=l)
			return 0;
		if (l==ll and r==rr)
			return ind;
		int lind = 0;
		int rind = 0;
		if (lft)
			lind = left->get(ll,rr);
		if (rgt)
			rind = right->get(ll,rr);
		if (h[lind]<h[rind])
			return lind;
		return rind;
	}
};



int power(int a,int b){
	if (b==0)
		return 1;
	int ans = power(a,b/2);
	ans = ans*ans;
	ans %= mod;
	if (b%2)
		ans = ans*a;
	return ans%mod;
}
 
int mod_inv(int k){
	return power(k,mod-2);
}
 
int asd(int a){
	int ans = (a*(a+1));
	ans = ans%mod;
	ans = ans*mod_inv(2);
	ans = ans% mod;
	return ans;
}

int answer(int W,int H){
	int ans = asd(W);
	int ans2 = asd(H);
	return (ans*ans2)%mod ;
}
node* root;
void solve(int l,int r,int height){
	if (r<l or l>r)
		return;
	int ind = root->get(l,r+1);
	int width = pre[r]-pre[l-1];
	if (width<0)
		width += mod;
	ans -= answer(width,height);
	if (ans<0)
		ans += mod;
	ans += answer(width,h[ind]);
	ans %= mod;
	solve(l,ind-1,h[ind]);
	solve(ind+1,r,h[ind]);
}

signed main(){
	h[0] = 2e9;
	root = new node(1,N+1);
	int n;
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>h[i];
		root->insert(i);
	}
	for (int i=1;i<=n;i++){
		cin>>w[i];
		pre[i] = pre[i-1] + w[i];
		pre[i] %= mod;
	}
	solve(1LL,n,0LL);

	cout<<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