Submission #954429

#	Time	Username	Problem	Language	Result	Execution time	Memory
954429		MinaRagy06	Fancy Fence (CEOI20_fancyfence)	C++17	30 / 100	1070 ms	2396 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) {
		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;
struct segtree {
	mint leaf[N];
	segtree() {
		for (int i = 0; i < N; i++) {
			leaf[i] = 1;
		}
	}
	void mult(int l, int r, mint v) {
		for (int i = l; i <= r; i++) {
			leaf[i] *= v;
		}
	}
	mint get(int l, int r) {
		mint s = 0;
		for (int i = l; i <= r; i++) {
			s += leaf[i];
		}
		return s;
	}
} seg, seg2;
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];
	}
	h[n] = -2e9;
	stack<int> s;
	s.push(n);
	mint ans = 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() - 1;
			mint v = mint(h[l]) / h[st];
			seg.mult(st, en, v);
			seg2.mult(st, en, v * v);
		}
		ans += (mint(w[l]) * (w[l] + 1) / 2) * (mint(h[l]) * (h[l] + 1) / 2);
		mint sum = seg.get(l + 1, n - 1) + seg2.get(l + 1, n - 1);
		sum *= w[l] / mint(2);
		ans += sum;
		s.push(l);
		seg.mult(l, l, mint(h[l]) * w[l]);
		seg2.mult(l, l, mint(h[l]) * h[l] * w[l]);
	}
	cout << ans << '\n';
	return 0;
}

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