oj.uz

Submission #772034

# Submission time Handle Problem Language Result Execution time Memory
772034 2023-07-03T14:29:43 Z RushB Fancy Fence (CEOI20_fancyfence) C++17
12 / 100
 1 ms 340 KB 
#include "bits/stdc++.h"
#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
using namespace std;
const long long INF = 1ll << 60;
const int N = 1e5 + 5;
const int M = 1e9 + 7;
int pw(int a) {
	return a * (a - 1) / 2 % M;
}
int H[N], W[N], n, ps[N], lt[N], rt[N];

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	FOR(i, 1, n + 1) cin >> H[i];
	FOR(i, 1, n + 1) cin >> W[i];
	vector<int> st{0};
	H[0] = H[n + 1] = -INF;
	FOR(i, 1, n + 1) {
		while (H[i] < H[st.back()]) st.pop_back();
		lt[i] = st.back();
		st.push_back(i);
	}
	st = {n + 1};
	for (int i = n; i >= 1; i--) {
		while (H[i] <= H[st.back()]) st.pop_back();
		rt[i] = st.back();
		st.push_back(i);
	}
	FOR(i, 1, n + 1) ps[i] = ps[i - 1] + W[i];
	int ans = 0;
	FOR(i, 1, n + 1) {
		int L = ps[i - 1] - ps[lt[i]] + 1;
		int R = ps[rt[i] - 1] - ps[i] + 1;
		int re = pw(L + R + W[i] - 1) - pw(L) - pw(R);
		ans += re % M * pw(H[i] + 1);
		//cout << "AT I: " << L << ' ' << R << endl;
	}
	ans %= M;
	if (ans < 0) ans += M;
	cout << ans << '\n';
	return 0;
}
//Reading this fills you with DETERMINATION
//17:10:32

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Incorrect 1 ms 336 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 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -