Submission #596247

#	Time	Username	Problem	Language	Result	Execution time	Memory
596247		kamelfanger83	Fancy Fence (CEOI20_fancyfence)	C++14	0 / 100	2 ms	340 KiB

fancyfence

#include <iostream>
#include <vector>
#include <limits>

#define int long long

using namespace std;

int module = 10e9+7;

struct segtree{
    vector<pair<int, int>> cache;
    segtree(int n){
        cache = vector<pair<int, int>> (n*4);
    }
    pair<int, int> build(int l, int r, int i, vector<int>& v){
        if(l + 1 == r) return cache[i] = {v[l], l};
        int m = l + (r-l)/2;
        return cache[i] = min(build(l, m, i*2+1, v), build(m, r, i*2+2, v)); 
    }
    pair<int, int> query(int l, int r, int i, int ql, int qr){
        if(qr <= l || r <= ql) return {numeric_limits<int>::max(), numeric_limits<int>::max()};
        if(ql <= l && r <= qr) return cache[i];
        int m = l + (r-l)/2;
        return min(query(l, m, i*2+1, ql, qr), query(m, r, i*2+2, ql, qr));
    }
};

signed main(){
    int n; cin >> n;
    vector<int> height (n);
    vector<int> width (n);
    for(int reader = 0; reader < n; reader++) cin >> height[reader];
    for(int reader = 0; reader < n; reader++) cin >> width[reader];

    segtree mint (n); mint.build(0, n, 0, height);
    vector<int> pref = {0}; for(int summer = 0; summer < n; summer++) pref.push_back(pref.back()+width[summer]); 

    auto from = [&](auto&& self, int l, int r, int to) -> pair<int, int>{
        if(l >= r) return {0,0};
        if(l+1 == r){
            int w = width[l], h = height[l] - to;
            int in = w*(w+1)/2;
            in %= module;
            in *= h;
            in %= module;
            in *= (h+1)/2;
            in %= module;
            int bot = w*(w+1)/2;
            bot %= module;
            bot *= h;
            bot %= module;
            return {in, bot};
        }
        vector<int> splits; int lowest = numeric_limits<int>::max(); int li = l;
        while(true){
            pair<int, int> got = mint.query(0, n, 0, li, r);
            if(got.first <= lowest){
                lowest = got.first;
                splits.push_back(got.second);
                li = got.second+1;
            }
            else{
                break;
            }
        }
        splits.push_back(r);
        int h = lowest-to;
        int w = pref[r] - pref[l];
        int sum_in = 0, sum_bot = 0;
        int prev = l;
        for(int seg : splits){
            pair<int, int> got = self(self, prev, seg, lowest);
            sum_in += got.first; sum_in %= module;
            sum_bot += got.second; sum_bot %= module;
            sum_in += got.second * h;
            prev = seg+1;
        }
        int in = w*(w+1)/2;
        in %= module;
        in *= h;
        in %= module;
        in *= (h+1)/2;
        in %= module;
        int bot = w*(w+1)/2;
        bot %= module;
        bot *= h;
        bot %= module;
        return {sum_in + in, sum_bot + bot};
    };
    pair<int, int> got = from(from, 0, n, 0);
    cout << got.first;
    return 0;
}

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