Submission #596363

#	Time	Username	Problem	Language	Result	Execution time	Memory
596363		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 = 1e9+7;

int fastpow(int b, int e){
    int res = 1;
    for(;e;e>>=1){
        if(e&1) res *= b;
        b *= b;
        res %= module; b %= module;
    }
    return res;
}

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;
    int half = fastpow(2, module-2);
    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]); 

#define mul(x, y) x *= y; x %= module

    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 = 1;
            mul(in, w);
            mul(in, w+1);
            mul(in, half);
            mul(in, h);
            mul(in, h+1);
            mul(in, half);
            int bot = 1;
            mul(bot, w);
            mul(bot, w+1);
            mul(bot, half);
            mul(bot, h);
            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;
        mul(in, w);
        mul(in, w+1);
        mul(in, half);
        mul(in, h);
        mul(in, h+1);
        mul(in, half);
        int bot;
        mul(bot, w);
        mul(bot, w+1);
        mul(bot, half);
        mul(bot, h);
        return {sum_in + in, sum_bot + bot};
    };
    pair<int, int> got = from(from, 0, n, 0);
    cout << got.first;
    return 0;
}

Compilation message (stderr)

fancyfence.cpp: In lambda function:
fancyfence.cpp:50:21: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 | #define mul(x, y) x *= y; x %= module
      |                     ^~
fancyfence.cpp:94:13: note: 'in' was declared here
   94 |         int in;
      |             ^~
fancyfence.cpp:50:21: warning: 'bot' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 | #define mul(x, y) x *= y; x %= module
      |                     ^~
fancyfence.cpp:101:13: note: 'bot' was declared here
  101 |         int bot;
      |             ^~~

• 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