Submission #970644

#	Time	Username	Problem	Language	Result	Execution time	Memory
970644		biximo	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	36 ms	7512 KiB

fancyfence

#include <bits/stdc++.h>
#define N 200005
using namespace std;
typedef long long ll;
ll wth[N], hgt[N], ans;
int p[N];
const int MOD = 1e9+7, DIV = (1e9+8)/4;
int get(int a) {
	if(p[a] != a) p[a]=get(p[a]);
	return p[a];
}
void join(int a, int b) {
	a = get(a); b = get(b);
	if(a == b) return;
	if(hgt[a] < hgt[b]) swap(a,b);
	ans += (1+wth[a])*(wth[a])%MOD*(hgt[a]+hgt[b]+1)%MOD*(hgt[a]-hgt[b])%MOD*DIV%MOD;
	ans %= MOD;
	wth[a] += wth[b];
	wth[a] %= MOD;
	hgt[a] = hgt[b];
	p[b] = a;
}
int H[N], W[N], order[N], n;
bool comp(int a, int b) {
	if(H[a] == H[b]) {
		return a > b;
	}
	return H[a] > H[b];
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i ++) {
    	cin >> H[i];
    }
    for(int i = 1; i <= n; i ++) {
    	cin >> W[i];
    	wth[i] = W[i];
    	hgt[i] = H[i];
    	order[i] = i;
    	p[i] = i;
    }
    sort(order+1, order+1+n,comp);
    for(int j = 1; j <= n; j ++) {
    	int i = order[j];
    	if(i-1>=1 && H[i-1] >= H[i]) {
    		join(i,i-1);
    	}
    	if(i+1<=n && H[i+1] >= H[i]) {
    		join(i,i+1);
    	}
    }
    join(0,1);
    if(ans < 0) ans += MOD;
    cout << ans;
}

• 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