Submission #1237460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237460		vuavisao	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	89 ms	3144 KiB

fancyfence

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

using ll = long long;

const int N = 100'000 + 10;
const int MOD = 1'000'000'000 + 7;

template <int Module>
class Mint {
private:
	int val;

public:
	Mint() : val(0) {};
	Mint(ll _val) {
		val = _val % Module;
		normalization_effect();
	}

public:
	void normalization_effect() {
		/// [- Module, 2 * Module)
		this->val = this->val + (this->val < 0) * Module - (this->val >= Module) * Module;
	}

	int get_val() const { return this->val; }

	Mint operator-() const { return Mint(-this->val); }

	Mint pw(ll exp) const {
		Mint res = 1;
		Mint base = *this;
		while (exp > 0) {
			if(exp & 1ll) res *= base;
			base *= base;
			exp >>= 1ll;
		}
		return res;
	}

	Mint inv() const {
		/// Module is prime
		/// return 〖val〗^(-1)
		return this->pw(Module - 2);
	}

public:
	Mint& operator+=(const Mint& other) {
		this->val += other.val;
		this->normalization_effect();
		return *this;
	}

	Mint& operator-=(const Mint& other) {
		this->val -= other.val;
		this->normalization_effect();
		return *this;
	}

	Mint& operator*=(const Mint& other) {
		this->val = 1ll * this->val * other.val % Module;
		this->normalization_effect();
		return *this;
	}

	Mint& operator/=(const Mint& other) {
		this->operator*=(other.inv());
		return *this;
	}

	Mint& operator++() { this->operator+=(1); return *this; }
	Mint& operator--() { this->operator-=(1); return *this; }

	Mint operator+(const Mint& other) const {
		Mint res = *this;
		res += other;
		return res;
	}

	Mint operator-(const Mint& other) const {
		Mint res = *this;
		res -= other;
		return res;
	}

	Mint operator*(const Mint& other) const {
		Mint res = *this;
		res *= other;
		return res;
	}

	Mint operator/(const Mint& other) const {
		Mint res = *this;
		res /= other;
		return res;
	}

	bool operator==(const Mint& other) const {
		return (this->val == other.val);
	}

public:
	friend ostream& operator<<(ostream& os, const Mint& other) {
		return os << other.val;
	}
};

using mint = Mint<MOD>;

int n;

ll h[N], w[N];

int le[N], ri[N];

mint sum(ll l, ll r) {
	if (l > r) return mint(0);
	return mint(r - l + 1) * (l + r) / 2;
}

ll get_pref(int l, int r) {
	if (l > r) return 0;
	return w[r] - w[l - 1];
}

int32_t main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> h[i];
	for (int i = 1; i <= n; ++i) cin >> w[i], w[i] += w[i - 1];
	stack<int> stk;
	stk.push(0);
	for (int i = 1; i <= n; ++i) {
		while (!stk.empty() && h[stk.top()] >= h[i]) stk.pop();
		le[i] = stk.top();
		stk.push(i);
	}
	while (!stk.empty()) stk.pop();
	
	stk.push(n + 1);
	for (int i = n; i >= 1; --i) {
		while (!stk.empty() && h[stk.top()] > h[i]) stk.pop();
		ri[i] = stk.top();
		stk.push(i);
	}
	// for (int i = 1; i <= n; ++i) {
	// 	cerr << i << ": " << le[i] << ' ' << ri[i] << '\n';
	// }
	mint res = 0;
	for (int i = 1; i <= n; ++i) {
		res += sum(1, h[i]) * get_pref(le[i] + 1, i - 1) * (w[i] - w[i - 1]);
		res += sum(1, h[i]) * (w[i] - w[i - 1]) * get_pref(i + 1, ri[i] - 1);
		res += sum(1, h[i]) * get_pref(le[i] + 1, i - 1) * get_pref(i + 1, ri[i] - 1);
		res += sum(1, h[i]) * sum(1, (w[i] - w[i - 1]));
		// cerr << "LEFT: " << sum(1, h[i]) * get_pref(le[i] + 1, i - 1) * (w[i] - w[i - 1]) << '\n';
		// cerr << "RIGHT: " << sum(1, h[i]) * (w[i] - w[i - 1]) * get_pref(i + 1, ri[i] - 1) << '\n';
		// cerr << "LEFT AND RIGHT: " << sum(1, h[i]) * get_pref(le[i] + 1, i - 1) * get_pref(i + 1, ri[i] - 1) << '\n';
		// cerr << "SELF: " << sum(1, h[i]) * sum(1, (w[i] - w[i - 1])) << '\n';
		// cerr << "VERTICAL: " << sum(1, h[i]) << '\n';
		// cerr << "LEFT: " << get_pref(le[i] + 1, i - 1) + 1 << ' ' << sum(1, (get_pref(le[i] + 1, i - 1) + 1)) << '\n';
		// cerr << "RIGHT: " << get_pref(i, ri[i] - 1) << ' ' << sum(1, get_pref(i, ri[i] - 1)) << '\n';
	}
	cout << res;
	return (0 ^ 0);
}

/// Code by vuavisao

• 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