Submission #954431

#	Time	Username	Problem	Language	Result	Execution time	Memory
954431		MinaRagy06	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	63 ms	3676 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int mod = 1e9 + 7;
struct mint {
	int v;
	mint() {
		v = 0;
	}
	mint(ll x) {
		if (x >= mod) {
			v = x % mod;
		} else {
			v = x;
		}
	}
	mint& operator+=(const mint &b) {
		if ((v += b.v) >= mod) {
			v -= mod;
		}
		return *this;
	}
	friend mint operator+(mint a, mint b) {
		return a += b;
	}
	mint& operator-=(const mint &b) {
		if ((v -= b.v) < 0) {
			v += mod;
		}
		return *this;
	}
	friend mint operator-(mint a, mint b) {
		return a -= b;
	}
	mint& operator*=(const mint &b) {
		v = 1ll * v * b.v % mod;
		return *this;
	}
	friend mint operator*(mint a, mint b) {
		return a *= b;
	}
	mint power(mint a, int b) {
		mint ans = 1;
		while (b) {
			if (b & 1) {
				ans *= a;
			}
			a *= a, b >>= 1;
		}
		return ans;
	}
	mint& operator/=(const mint &b) {
		v = 1ll * v * power(b, mod - 2).v % mod;
		return *this;
	}
	friend mint operator/(mint a, mint b) {
		return a /= b;
	}
	friend ostream& operator<<(ostream &os, mint a) {
		return os << a.v;
	}
	friend istream& operator>>(istream &is, mint &a) {
		return is >> a.v;
	}
};
const int N = 100'005;
mint prf[N];
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	int h[n + 1], w[n];
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> w[i];
	}
	for (int i = 0; i < n; i++) {
		prf[i + 1] = prf[i] + w[i];
	}
	h[n] = -2e9;
	stack<int> s;
	s.push(n);
	mint ans = 0, sum = 0;
	for (int l = n - 1; l >= 0; l--) {
		while (h[l] <= h[s.top()]) {
			int st = s.top();
			s.pop();
			int en = s.top();
			sum -= (prf[en] - prf[st]) * h[st];
			sum -= (prf[en] - prf[st]) * h[st] * h[st];
			sum += (prf[en] - prf[st]) * h[l];
			sum += (prf[en] - prf[st]) * h[l] * h[l];
		}
		ans += (mint(w[l]) * (w[l] + 1) / 2) * (mint(h[l]) * (h[l] + 1) / 2);
		ans += sum * w[l] / mint(2);
		s.push(l);
		sum += mint(h[l]) * w[l];
		sum += mint(h[l]) * h[l] * w[l];
	}
	cout << ans << '\n';
	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