oj.uz

Submission #954431

# Submission time Handle Problem Language Result Execution time Memory
954431 2024-03-27T21:25:12 Z MinaRagy06 Fancy Fence (CEOI20_fancyfence) C++17
100 / 100
 63 ms 3676 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 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 29 ms 1236 KB Output is correct
4 Correct 57 ms 1628 KB Output is correct
5 Correct 57 ms 1880 KB Output is correct
6 Correct 59 ms 1628 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 7 ms 924 KB Output is correct
3 Correct 30 ms 1116 KB Output is correct
4 Correct 61 ms 3536 KB Output is correct
5 Correct 61 ms 3676 KB Output is correct
6 Correct 1 ms 856 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 7 ms 860 KB Output is correct
4 Correct 31 ms 1124 KB Output is correct
5 Correct 60 ms 3420 KB Output is correct
6 Correct 62 ms 3652 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 6 ms 1116 KB Output is correct
9 Correct 31 ms 2140 KB Output is correct
10 Correct 60 ms 3396 KB Output is correct
11 Correct 60 ms 3420 KB Output is correct
12 Correct 0 ms 604 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 0 ms 604 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 29 ms 1116 KB Output is correct
12 Correct 60 ms 2652 KB Output is correct
13 Correct 58 ms 2648 KB Output is correct
14 Correct 57 ms 2652 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 7 ms 1116 KB Output is correct
17 Correct 32 ms 2120 KB Output is correct
18 Correct 61 ms 3396 KB Output is correct
19 Correct 61 ms 3408 KB Output is correct
20 Correct 1 ms 860 KB Output is correct
21 Correct 7 ms 1116 KB Output is correct
22 Correct 31 ms 2120 KB Output is correct
23 Correct 60 ms 3420 KB Output is correct
24 Correct 61 ms 3528 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 856 KB Output is correct
27 Correct 1 ms 856 KB Output is correct
28 Correct 1 ms 860 KB Output is correct
29 Correct 1 ms 860 KB Output is correct
30 Correct 7 ms 1312 KB Output is correct
31 Correct 8 ms 1272 KB Output is correct
32 Correct 31 ms 2116 KB Output is correct
33 Correct 31 ms 2136 KB Output is correct
34 Correct 60 ms 3280 KB Output is correct
35 Correct 61 ms 3164 KB Output is correct
36 Correct 61 ms 3416 KB Output is correct
37 Correct 61 ms 3416 KB Output is correct
38 Correct 1 ms 856 KB Output is correct
39 Correct 61 ms 3404 KB Output is correct
40 Correct 63 ms 3552 KB Output is correct
41 Correct 60 ms 3416 KB Output is correct
42 Correct 60 ms 3664 KB Output is correct