Submission #961806

#	Time	Username	Problem	Language	Result	Execution time	Memory
961806		starchan	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	36 ms	8444 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int mod = 1e9+7;
const int MX = 1e5+5;

int c2(int x)
{
	return ((x*(x+1))/2)%mod;
}

int sum;
vector<int> pa(MX, -1);
vector<int> dp(MX, 0);

int leader(int u)
{
	if(pa[u] < 0)
		return u;
	else
		return pa[u] = leader(pa[u]);
}

void merge(int u, int v)
{
	u = leader(u); v = leader(v);
	if(u==v)
		return;
	if(pa[u] < pa[v])
		swap(u, v);
	pa[v]+=pa[u];
	sum+=((dp[u]*dp[v])%mod); sum%=mod;
	dp[v]+=dp[u]; dp[v]%=mod;
	pa[u] = v;
	return;
}
signed main()
{
	fast();
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> b(n);
	vector<in> ab(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		ab[i][0] = a[i];
	}
	for(int i = 0; i < n; i++)
	{
		cin >> b[i];
		ab[i][1] = i;
	}
	sort(ab.rbegin(), ab.rend());
	vector<int> C{ab[0][0]};
	for(auto p: ab)
	{
		if(C.back() != p[0])
			C.pb(p[0]);
	}
	int ans = 0;
	int l = 0; int D = C.size(); C.pb(0);
	for(int i = 0; i < D; i++)
	{
		int L = l;
		while((l < n) && (ab[l][0] >= C[i]))
		{
			int lp = ab[l][1];
			dp[lp] = b[lp];
			sum+=c2(b[lp]);
			sum%=mod;
			l++;
		}
		l = L;
		while((l < n) && (ab[l][0] >= C[i]))
		{
			int lp = ab[l][1];
			if(((lp+1) < n) && (a[lp+1] >= C[i]))
				merge(lp, lp+1);
			if(((lp-1) >= 0) && (a[lp-1] >= C[i]))
				merge(lp, lp-1);
			l++;
		}
		int val = (sum*((c2(C[i])-c2(C[i+1])+mod)%mod))%mod;
		ans+=val; ans%=mod;
	}
	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