oj.uz

Submission #954430

# Submission time Handle Problem Language Result Execution time Memory
954430 2024-03-27T21:24:07 Z MinaRagy06 Fancy Fence (CEOI20_fancyfence) C++17
25 / 100
 59 ms 2772 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 856 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 29 ms 1116 KB Output is correct
4 Correct 57 ms 2768 KB Output is correct
5 Correct 59 ms 2772 KB Output is correct
6 Correct 57 ms 2652 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -