oj.uz

Submission #596402

# Submission time Handle Problem Language Result Execution time Memory
596402 2022-07-14T17:11:49 Z kamelfanger83 Fancy Fence (CEOI20_fancyfence) C++14
27 / 100
 104 ms 12480 KB 
#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%module); 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; sum_in %= module;
            prev = seg+1;
        }
        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 {sum_in + in, sum_bot + bot};
    };
    pair<int, int> got = from(from, 0, n, 0);
    cout << got.first;
    return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 216 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 13 ms 1544 KB Output is correct
3 Correct 49 ms 6280 KB Output is correct
4 Correct 90 ms 12332 KB Output is correct
5 Correct 104 ms 12476 KB Output is correct
6 Correct 0 ms 304 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 10 ms 1492 KB Output is correct
4 Correct 52 ms 6264 KB Output is correct
5 Correct 89 ms 12344 KB Output is correct
6 Correct 88 ms 12480 KB Output is correct
7 Incorrect 2 ms 596 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -