Submission #294537

#	Time	Username	Problem	Language	Result	Execution time	Memory
294537		nandonathaniel	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	99 ms	9336 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
const LL MAXN=1e5+5,MOD=1e9+7;

LL h[MAXN],w[MAXN],tree[4*MAXN],par[MAXN],sz[MAXN];
bool ada[MAXN];
pii arr[MAXN];

LL find(LL x){
	if(par[x]==x)return par[x];
	return par[x]=find(par[x]);
}

void join(LL u,LL v){
	LL repu=find(u),repv=find(v);
	par[repu]=repv;
	sz[repv]+=sz[repu];
}

void build(LL now,LL L,LL R){
	if(L==R){
		tree[now]=w[L];
		return;
	}
	LL mid=(L+R)/2;
	build(2*now,L,mid);
	build(2*now+1,mid+1,R);
	tree[now]=tree[2*now]+tree[2*now+1];
}

LL query(LL now,LL L,LL R,LL x,LL y){
	if(L>=x && R<=y)return tree[now];
	if(L>y || R<x)return 0;
	LL mid=(L+R)/2;
	return query(2*now,L,mid,x,y)+query(2*now+1,mid+1,R,x,y);
}

LL C(LL x){
	LL p=x%MOD,q=(x-1)%MOD;
	return (((p*q)%MOD)*500000004)%MOD;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	LL n,ans=0;
	cin >> n;
	for(LL i=1;i<=n;i++)cin >> h[i];
	for(LL i=1;i<=n;i++){
		cin >> w[i];
		LL ret=(C(h[i]+1)*C(w[i]+1))%MOD;
		ans=(ans+ret)%MOD;
	}
	build(1,1,n);
	for(LL i=1;i<=n;i++){
		h[i]++;
		arr[i]={h[i],i};
		par[i]=i;
		sz[i]=1;
	}
	sort(arr+1,arr+n+1);
	reverse(arr+1,arr+n+1);
	for(LL i=1;i<=n;i++){
		pii isi=arr[i];
		LL kiri=0,kanan=0;
		if(ada[isi.second-1]){
			kiri=sz[find(isi.second-1)];
			join(isi.second,isi.second-1);
		}
		if(ada[isi.second+1]){
			kanan=sz[find(isi.second+1)];
			join(isi.second,isi.second+1);
		}
		LL totL=query(1,1,n,isi.second-kiri,isi.second)%MOD,totR=query(1,1,n,isi.second,isi.second+kanan)%MOD;
		LL sum=(((totL*totR)%MOD)-((w[isi.second]*w[isi.second])%MOD)+MOD)%MOD;
		ans=(ans+((sum*C(isi.first))%MOD))%MOD;
		ada[isi.second]=true;
	}
	cout << ans << '\n';
	return 0;
}

• 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