Submission #598272

#	Time	Username	Problem	Language	Result	Execution time	Memory
598272		_Avocado_	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	49 ms	6656 KiB

fancyfence

#include <bits/stdc++.h>
#define int int64_t
using namespace std;

int mod = 1e9+7;
int ans = 0;

int sum(int n){
	n %= mod;
	return (((n*(n+1)))/2)%mod;
}

int find(int a, auto&par){
	if(a == par[a]) return a;
	return par[a] = find(par[a], par);
}

void unite(int a, int b, int h, auto&par, auto&w){
	a = find(a, par);
	b = find(b, par);
	int minus = (((sum(w[a]) * sum(h))%mod) + (sum(w[b]) * sum(h)))%mod;
	//cout<<"minus "<<minus<<endl;
	ans = (ans + ((sum(w[a] + w[b]) * sum(h))%mod - minus + mod)%mod)%mod;
	
	par[b] = a;
	w[a] = (w[a] + w[b])%mod;
	
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin ("input.in");
	//ofstream cout ("output.out");
	
	int n; cin>>n;
	vector<pair<int, int>>height(n);
	vector<int>w(n);
	
	for(int i = 0; i<n; ++i){
		int a; cin>>a;
		height[i] = {a, i};
	}
	for(auto&u: w) cin>>u;
	
	for(int i = 0; i<n; ++i){
		ans = (ans + (sum(height[i].first) * sum(w[i]))%mod)%mod;
	}
	//cout<<ans<<endl;
	vector<int>par(n);
	iota(par.begin(), par.end(), 0);
	vector<int>fred(n);
	
	sort(height.begin(), height.end());
	reverse(height.begin(), height.end());
	
	for(int i = 0; i<n; ++i){
		int cur = height[i].second;
		if(cur != 0 && fred[cur-1]) unite(cur, cur-1, height[i].first, par, w);
		if(cur != n-1 && fred[cur+1]) unite(cur, cur+1, height[i].first, par, w);
		fred[cur] = 1;
	}
	cout<<ans;	
	cout<<'\n';
}

Compilation message (stderr)

fancyfence.cpp:13:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   13 | int find(int a, auto&par){
      |                 ^~~~
fancyfence.cpp:18:33: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void unite(int a, int b, int h, auto&par, auto&w){
      |                                 ^~~~
fancyfence.cpp:18:43: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void unite(int a, int b, int h, auto&par, auto&w){
      |                                           ^~~~

• 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