Submission #1262547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262547		kerem	Fancy Fence (CEOI20_fancyfence)	C++20	0 / 100	1 ms	328 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 100000

const int mod=1e9+7;
const int inv2=500000004;
int dsu[N+5],act[N+5],len=0;

int calc(int x){
	return x*(x-1)%mod*inv2%mod;
}
int calc(int l,int r){
	return (r-l+1)*(l+r)%mod*inv2%mod;
}
int find(int x){
	if(dsu[x]>0)
		return -x;
	return dsu[x]=find(-dsu[x]);
}
void comb(int x,int y){
	x=-find(x);y=-find(y);
	
	len=(len-calc(dsu[x]+1)+mod)%mod;
	len=(len-calc(dsu[y]+1)+mod)%mod;
	
	dsu[x]=(dsu[x]+dsu[y])%mod;
	len=(len+calc(dsu[x]+1))%mod;
	dsu[y]=-x;
}
void upt(int d,int it){
	act[it]=1;
	len=(len+calc(d+1))%mod;
	if(act[it-1]) comb(it,it-1);
	if(act[it+1]) comb(it,it+1);
}
int32_t main(){
	int n;
	cin >> n;
	vector<pair<int,int>> h(n,pair<int,int>());
	for(int i=0;i<n;i++){
		cin >> h[i].fr;
		h[i].sc=i+1;
	}
	for(int i=1;i<=n;i++)
		cin >> dsu[i];
	sort(all(h),greater<pair<int,int>>());
	h.pb({0,0});
	int ans=0;
	for(int i=0;i<n;i++){
		while(i<n  && h[i].fr==h[i+1].fr)
			upt(h[i].fr,h[i].sc),i++;
		upt(h[i].fr,h[i].sc);
		ans=(ans+(calc(h[i+1].fr+1,h[i].fr)*len%mod))%mod;
	}
	cout << ans << endl;
}

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