Submission #970633

#	Time	Username	Problem	Language	Result	Execution time	Memory
970633		biximo	Fancy Fence (CEOI20_fancyfence)	C++17	15 / 100	22 ms	8788 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)/2;
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*DIV%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);
    for(int j = 1; j <= n; j ++) {
    	int i = order[j];
    	if(i-1 && !comp(i-1, i)) {
    		join(i,i-1);
    	}
    	if(i+1<=n && !comp(i+1, i)) {
    		join(i,i+1);
    	}
    }
    int i = get(1);
    ans += wth[i]*hgt[i]%MOD*(wth[i]+1)%MOD*(hgt[i]+1)%MOD*DIV%MOD*DIV%MOD;
    ans %= MOD;
    if(ans < 0) ans += MOD;
    cout << ans;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27