제출 #1231490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231490		g4yuhg	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	41 ms	5824 KiB

fancyfence

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 300005
using namespace std;

bool ghuy4g;

const ll mod = 1e9 + 7;

ll n;
ll h[N], w[N], L[N], R[N], pf[N];
vector<ll> vt;
bool cmp(ll a, ll b) {
	if (h[a] == h[b]) {
		return a > b;
	}
	return h[a] < h[b];
}

void pre() { // li: thang xa nhat nho hon no
	stack<ll> st;
	for (int i = 1; i <= n; i ++) {
		while (st.size() && h[st.top()] >= h[i]) {
			st.pop();
		}
		if (st.size()) L[i] = st.top();
		st.push(i);
		vt.push_back(i);
	}
	while (st.size()) st.pop();
	for (int i = n; i >= 1; i --) {
		while (st.size() && h[st.top()] > h[i]) {
			st.pop();
		}
		if (st.size()) R[i] = st.top();
		else R[i] = n + 1;
		st.push(i);
		//cout << i << " " << L[i] << " " << R[i] << endl;
	}
	sort(vt.begin(), vt.end(), cmp);
}

/*void solve() {
	ll ans = 0;
	ll prev_h = 0;
	for (auto it : vt) {
		//ll 
		prev_h = max(h[R[it]], h[L[it]]);
		ll W = h[it] - prev_h, Y = pf[R[it] - 1] - pf[L[it]];
		ans += (W * (W + 1) / 2 * Y * (Y + 1) / 2);
		ll xet = Y * (Y + 1) / 2 * W * prev_h;
		ans += xet;
		//cout << it << " " << L[it] << " " << R[it] << " WY " << W << " " << Y << " " << ans << " " << xet << endl;
		prev_h = h[it];
	}
	cout << ans << endl;
}*/

void solve() {
    ll ans = 0;
    ll prev_h = 0;
    for (auto it : vt) {
        prev_h = max(h[R[it]], h[L[it]]);
        ll W = (h[it] - prev_h) % mod;
        ll Y = (pf[R[it] - 1] - pf[L[it]] + mod) % mod;
        ll halfW = W * ((W + 1) % mod) % mod * ((mod + 1) / 2) % mod;
        ll halfY = Y * ((Y + 1) % mod) % mod * ((mod + 1) / 2) % mod;
        ll term1 = halfW * halfY % mod;
        ans = (ans + term1) % mod;
        ll term2 = halfY * W % mod * prev_h % mod;
        ans = (ans + term2) % mod;
        prev_h = h[it];
    }
    cout << ans % mod << endl;
}

bool klinh;

signed main(void) {
    faster;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> h[i];
	}
	for (int i = 1; i <= n; i ++) {
		cin >> w[i];
		pf[i] = pf[i - 1] + w[i];
	}
	pre();
	solve();
    cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
    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