Submission #1336358

#TimeUsernameProblemLanguageResultExecution timeMemory
1336358liptonekFancy Fence (CEOI20_fancyfence)C++20
100 / 100
18 ms3544 KiB
#include <bits/stdc++.h>
using namespace std;

const long long MOD=1e9+7;
const long long INV2=500000004;

struct Section
{
    long long h,w;
};

long long tri(long long n)
{
    n%=MOD;

    return n*(n+1)%MOD*INV2%MOD;
}

long long f(long long h, long long w)
{
    return tri(h)*tri(w)%MOD;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;

    vector<long long> h(n);
    vector<long long> w(n);

    for(int i=0; i<n; i++)
    {
        cin>>h[i];
    }

    for(int i=0; i<n; i++)
    {
        cin>>w[i];
    }

    stack<Section> s;

    s.push({0,0});

    long long total=0;

    for(int i=0; i<=n; i++)
    {
        long long ch=(i==n) ? 0 : h[i];
        long long cw=(i==n) ? 0 : w[i];

        long long accumulated=0;

        while(s.top().h>ch)
        {
            Section top=s.top();
            s.pop();

            long long next=max(s.top().h,ch);
            long long width=(top.w+accumulated)%MOD;
            long long term=(f(top.h,width)-f(next,width)+MOD)%MOD;

            total=(total+term)%MOD;

            accumulated=width;
        }

        s.push({ch,(cw+accumulated)%MOD});
    }

    cout<<total<<endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...