Submission #697054

#	Time	Username	Problem	Language	Result	Execution time	Memory
697054		vjudge1	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	65 ms	6856 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
const int mod=1e9+7, maxn=1e6+5;
ll n, h[maxn], lebar[maxn], par[maxn], sz[maxn], kiri, kanan, w, t, ans, last, v[maxn];
bool vis[maxn];

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

void join(int u, int v) {
	int ou=find(u), ov=find(v);
	if(ou!=ov) {
		par[ou]=ov;
		sz[ov]+=sz[ou];
		lebar[ov]+=lebar[ou];
	}
}

ll p(ll a, ll b) {
	ll res=1;
	while(b) {
		if(b%2) res=(res*a)%mod;
		a=(a*a)%mod;
		b/=2;
	}
	return res;
}

ll deret(ll a, ll b) {
	ll n=(b-a+1)%mod;
	return (((n*((a+b)%mod))%mod)*p(2, mod-2))%mod;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for(int i=1; i<=n; i++) {
		cin >> h[i];
		v[i]=par[i]=i;
		sz[i]=1;
	}
	for(int i=1; i<=n; i++) cin >> lebar[i];
	sort(v+1, v+n+1, [](auto ki, auto ka) {
		return h[ki]>h[ka];
	});
	last=1;
	for(int i=1; i<=n; i++) {
		if(i==n||h[v[i]]>h[v[i+1]]) {
			for(int j=last; j<=i; j++) {
				if(h[v[j]]<=h[v[j]-1]) join(v[j], v[j]-1);
				if(h[v[j]]<=h[v[j]+1]) join(v[j]+1, v[j]);
			}
			for(int j=last; j<=i; j++) {
				kiri=find(v[j]);
				if(vis[kiri]) continue;
				kanan=kiri+sz[kiri]-1, w=lebar[kiri], t=h[v[j]];
				// cout << v[j] << ' ' << t << ' ' << w << '\n';
				ans=(((deret(max(h[kiri-1], h[kanan+1])+1, t)*deret(1, w))%mod)+ans)%mod;
				vis[kiri]=true;
			}
			for(int j=last; j<=i; j++) vis[find(v[j])]=false;
			last=i+1;
		}
	}
	cout << ans << '\n';
}

• 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