Submission #970642

#TimeUsernameProblemLanguageResultExecution timeMemory
970642biximoFancy Fence (CEOI20_fancyfence)C++17
15 / 100
22 ms5468 KiB
#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>=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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...