Submission #427800

#TimeUsernameProblemLanguageResultExecution timeMemory
427800OzyFancy Fence (CEOI20_fancyfence)C++17
12 / 100
1 ms340 KiB
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (lli i = (a); i <= (b); i++)
#define repa(i,a,b) for (lli i = (a); i >= (b); i--)
#define debugsl(a) cout << #a << " = " << a << ", "
#define debug(a) cout << #a << " = " << a << endl

#define altura first
#define pos second
#define MAX 100000
#define mod 1000000007

lli n,res,ult,act,a,w,pas;
lli h[MAX+2];
stack<pair<lli,lli> > pila;
pair<lli,lli> k;

lli calcula(lli f, lli c) {

    lli a = (f*(f+1))/2;
    a %= mod;
    lli b = (c*(c+1))/2;
    b %= mod;

    a *= b;
    a %= mod;

    return a;
}

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

    cin >> n;
    rep(i,1,n) cin >> h[i];

    act = 1;
    pila.push({0,0});

    rep(i,1,n) {

        cin >> w;

        pas = act;
        while (!pila.empty() && pila.top().altura > h[i]) {

            k = pila.top();
            pila.pop();

            pas = k.pos;
            a = act-k.pos;
            res += calcula(a, k.altura);
            res -= calcula(a, max(pila.top().altura, h[i]));

            if (res < 0) res += mod;
            res %= mod;

        }

        act += w;
        if (pila.top().altura == h[i]) continue;
        else (pila.push({h[i],pas}));

    }

    while (!pila.empty()) {

        k = pila.top();
        pila.pop();
        if (k.altura == 0) break;

        pas = k.pos;
        a = act-k.pos;
        res += calcula(a, k.altura);
        res -= calcula(a, pila.top().altura);

        if (res < 0) res += mod;
        res %= mod;

    }

    cout << res;
}
#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...