This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1e9 + 7;
int n, h[100006], w[100006], res, sum[100006];
vector<int> v;
int get(int x, int y) {
return (sum[y] - (x ? sum[x - 1] : 0) + MOD) % MOD;
}
pair<int, int> tree[262144];
pair<int, int> query(int i, int b, int e, int l, int r) {
if (r < l || r < b || e < l) return { (int)1e9, -1 };
if (l <= b && e <= r) return tree[i];
int m = (b + e) / 2;
return min(query(i * 2 + 1, b, m, l, r), query(i * 2 + 2, m + 1, e, l, r));
}
void dnc(int l, int r, int curr) {
if (l > r) return;
int m = query(0, 0, 131071, l, r).second;
int x = (1LL * h[m] * (h[m] + 1) / 2 % MOD - 1LL * curr * (curr + 1) / 2 % MOD + MOD) % MOD;
res = (res + 1LL * x * (1LL * get(l, r) * (get(l, r) + 1) / 2 % MOD) % MOD) % MOD;
dnc(l, m - 1, h[m]);
dnc(m + 1, r, h[m]);
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", h + i);
for (int i = 0; i < n; i++) scanf("%d", w + i);
sum[0] = w[0];
for (int i = 1; i < n; i++) sum[i] = (sum[i - 1] + w[i]) % MOD;
for (int i = 0; i < n; i++) tree[131071 + i] = { h[i], i };
for (int i = 131070; i >= 0; i--) tree[i] = min(tree[i * 2 + 1], tree[i * 2 + 2]);
dnc(0, n - 1, 0);
printf("%d", res);
}
Compilation message (stderr)
fancyfence.cpp: In function 'int main()':
fancyfence.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
fancyfence.cpp:35:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | for (int i = 0; i < n; i++) scanf("%d", h + i);
| ~~~~~^~~~~~~~~~~~~
fancyfence.cpp:36:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | for (int i = 0; i < n; i++) scanf("%d", w + i);
| ~~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |