Submission #891894

#	Time	Username	Problem	Language	Result	Execution time	Memory
891894		asdasdqwer	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	25 ms	11088 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define pii pair<int,int>

const int MOD = 1e9 + 7;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;cin>>n;
    vector<int> h(n), w(n);
    for (int &x:h)cin>>x;
    for (int &x:w)cin>>x;
    vector<bool> era(n, false);
    vector<int> pv(n, 0);
    for (int i=1;i<n;i++) {
        if (h[i] == h[i-1]) {
            era[i]=true;
            pv[i]=pv[i-1];
            w[pv[i]]+=w[i];
        }

        else {
            pv[i]=i;
        }
    }

    vector<int> th, tw;
    for (int i=0;i<n;i++) {
        if (!era[i]) {
            th.push_back(h[i]);
            tw.push_back(w[i]);
        }
    }

    w=tw;h=th;
    n = w.size();
    vector<bool> ign(n, false);
    stack<array<int,2>> s;

    vector<int> p(n);
    p[0]=w[0];
    for (int i=1;i<n;i++) p[i]=p[i-1]+w[i];

    vector<int> st(n, 0), en(n, 0), clos(n, 0);

    for (int i=0;i<n;i++) {
        while (s.size() && s.top()[0] >= h[i]) {
            if (s.top()[0] == h[i]) {
                ign[i]=true;
            }

            s.pop();
        }

        if (s.size() == 0) {
            st[i] = 0;
        }

        else {
            st[i] = s.top()[1];
            clos[i] = s.top()[0];
        }

        s.push({h[i], p[i]});
    }

    while (s.size())s.pop();

    for (int i=n-1;i>=0;i--) {
        while (s.size() && s.top()[0] >= h[i]) {
            s.pop();
        }

        if (s.size() == 0) {
            en[i] = p.back();
        }

        else {
            en[i] = s.top()[1];
            
            if (clos[i] == 0) {
                clos[i] = s.top()[0];
            }

            else {
                clos[i] = max(clos[i], s.top()[0]);
            }
        }

        if (i != 0) s.push({h[i], p[i-1]});
    }

    // for (int i=0;i<n;i++) {
    //     cout<<st[i]<<" "<<en[i]<<" "<<clos[i]<<" "<<ign[i]<<"\n";
    // }

    int res=0;

    for (int i=0;i<n;i++) {
        if (ign[i])continue;
        int lenBase = en[i] - st[i] + 1;
        int height = h[i];

        int bases = (lenBase) % MOD;
        bases = (bases * (bases-1)) % MOD;
        bases = (500000004 * bases) % MOD;

        int fullHeight = (height+1) % MOD;
        fullHeight = (fullHeight * (fullHeight - 1)) % MOD;
        fullHeight = (500000004 * fullHeight) % MOD;

        int fullRect = (fullHeight * bases) % MOD;

        int partHeight = (clos[i]+1) % MOD;
        partHeight = (partHeight * (partHeight - 1)) % MOD;
        partHeight = (500000004 * partHeight) % MOD;

        fullRect -= ((partHeight * bases) % MOD);
        fullRect += 2*MOD;
        fullRect %= MOD;

        res += fullRect;
    }

    res %= MOD;
    cout<<res<<"\n";
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27