Submission #750701

#	Time	Username	Problem	Language	Result	Execution time	Memory
750701		inventiontime	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	76 ms	25028 KiB

fancyfence

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

#define int ll
#define endl '\n' //comment for interactive
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define pb push_back
#define re resize
#define ff first
#define ss second

#define all(x) (x).begin(), (x).end()
#define all1(x) (x).begin()+1, (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)

#define print(x) cout << #x << ": " << x << endl << flush

typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
typedef array<int, 3> ti;
typedef vector<ii> vii;
typedef vector<ti> vti;
typedef vector<vi> vvi;
typedef priority_queue<int> pq;

template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }

const int inf = 1e17;
const int mod = 1e9+7;

struct min_st {
    
    vii tree;
    int left, right;
    min_st(vi x) : tree(x.size()*4) {
        left = 0;
        right = x.size()-1;
        _build(1, left, right, x);
    }

    void _build(int node, int l, int r, vi& x) {
        if(l == r) {
            tree[node] = {x[l], l};
            return;
        }
        int m = (l+r)/2;
        _build(node*2, l, m, x);
        _build(node*2+1, m+1, r, x);
        tree[node] = min(tree[node*2], tree[node*2+1]);
    }

    ii _query(int node, int l, int r, int ql, int qr) {
        if(ql <= l and r <= qr) return tree[node];
        if(r < ql or qr < l) return {inf, inf};
        int m = (l+r)/2;
        return min(
            _query(node*2, l, m, ql, qr),
            _query(node*2+1, m+1, r, ql, qr));
    }

    ii query(int ql, int qr) {
        return _query(1, left, right, ql, qr);
    }

};

int power(ll x, int y) {
    int res = 1;

    x = x % mod;

    while(y > 0) {
        if(y & 1)
            res = ((ll)res*x) % mod;

        y = y >> 1;
        x = (x*x) % mod;
    }

    return res;
}

int inv(int n) {
    return power(n, mod-2);
}

int mm(int x, int y) {
    x %= mod, y %= mod;
    return (x * y) % mod;
}

int nc2(int n) {
    return mm(mm(n, (n-1)), inv(2));
}

void solve() {

    int n;
    cin >> n;
    vi h(n+1), w(n+1);
    loop1(i, n)
        cin >> h[i];
    loop1(i, n)
        cin >> w[i];
    vi pw(n+1);
    loop1(i, n) {
        pw[i] = pw[i-1] + w[i];
        pw[i] %= mod;
    }

    min_st st(h);
    auto calc = [&] (int l, int r, auto calc) -> int {
        if(r < l) return 0;
        auto [mh, mi] = st.query(l, r);
        return
            (mm(nc2(mh+1), nc2(w[mi] + 1))
            + mm(nc2(mh+1), mm(pw[mi-1] - pw[l-1], w[mi]))
            + mm(nc2(mh+1), mm(pw[r] - pw[mi], w[mi]))
            + mm(nc2(mh+1), mm(pw[mi-1] - pw[l-1], pw[r] - pw[mi]))
            + calc(l, mi-1, calc) 
            + calc(mi+1, r, calc)) % mod;
    };
    
    cout << ((calc(1, n, calc) + mod) % mod) << endl;

}

signed main() {

    fast_io;

    int t = 1; //cin >> t;
    while(t--)
        solve();

    return 0;

}

• 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