# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1013592 | daffuwu | Fancy Fence (CEOI20_fancyfence) | C++14 | 27 ms | 5456 KiB |
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 <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long n, h[100069], w, dp[100069], ans, ps[100069];
const long long dv = 1e9+7;
stack<long long> stk;
long long calc(long long a, long long b)
{
if (a%2 == 0) a/=2;
else b/=2;
return a%dv*(b%dv)%dv;
}
int main()
{
long long i, j;
scanf("%lld", &n);
for (i=1; i<=n; i++)
{
scanf("%lld", h+i);
}
stk.push(0);
for (i=1; i<=n; i++)
{
scanf("%lld", &w);
ps[i] = ps[i-1]+w;
for (; h[i]<=h[stk.top()]; stk.pop());
j = stk.top();
ans += (calc(ps[i]-ps[j], ps[i]-ps[j]+1)-calc(ps[i-1]-ps[j], ps[i-1]-ps[j]+1))*calc(h[i], h[i]+1)%dv;
ans += dp[j]*w%dv;
ans %= dv;
dp[i] = (dp[j]+calc(h[i], h[i]+1)*((ps[i]-ps[j])%dv)%dv)%dv;
stk.push(i);
}
if (ans<0) ans += dv;
printf("%lld\n", ans);
}
Compilation message (stderr)
# | 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... |