제출 #1262553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262553		kerem	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	61 ms	4296 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 it){
	act[it]=1;
	len=(len+calc(dsu[it]+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].sc),i++;
		upt(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: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27