# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
855515 | sofijavelkovska | Fancy Fence (CEOI20_fancyfence) | C++14 | 1 ms | 604 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;
const long long MAXN=1e5, MOD=1e9+7;
long long h[MAXN], w[MAXN];
bool compare(long long x, long long y)
{
return h[x]<=h[y];
}
long long outer(long long i, long long sum)
{
return (long long)h[i]*w[i]%MOD*sum%MOD;
}
long long inner(long long i)
{
long long rectangles=0;
rectangles=(rectangles+(long long)h[i]*w[i])%MOD;
rectangles=(rectangles+h[i]*((long long)w[i]*(w[i]-1)/2%MOD)%MOD)%MOD;
rectangles=(rectangles+w[i]*((long long)h[i]*(h[i]-1)/2%MOD)%MOD)%MOD;
rectangles=(rectangles+((long long)h[i]*(h[i]-1)/2%MOD)*((long long)w[i]*(w[i]-1)/2%MOD)%MOD)%MOD;
return rectangles;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
long long n, x, left, right, i;
long long leftsum, rightsum, total=0;
set<long long> processed;
cin >> n;
long long index[i];
long long prefixsum[n];
for (i=0; i<n; i++)
cin >> h[i];
for (i=0; i<n; i++)
cin >> w[i];
for (i=0; i<n; i++)
index[i]=i;
sort(index, index+n, compare);
prefixsum[0]=w[0];
for (i=1; i<n; i++)
prefixsum[i]=prefixsum[i-1]+w[i];
processed.insert(-1);
processed.insert(n);
for (i=0; i<n; i++)
{
x=index[i];
auto it=processed.lower_bound(x);
right=*it;
it--;
left=*it;
rightsum=prefixsum[right-1]-prefixsum[x];
leftsum=prefixsum[x]-w[x]-(prefixsum[left+1]-w[left+1]) ;
total=(total+outer(x, leftsum)+outer(x, rightsum)+inner(x))%MOD;
processed.insert(x);
}
cout << total;
return 0;
}
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... |