Submission #793222

#	Time	Username	Problem	Language	Result	Execution time	Memory
793222		SlavicG	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	35 ms	25816 KiB

fancyfence

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

#define int long long
const int N = 1e5 + 5, mod = 1e9 + 7, K = 17;
int ans = 0;
int jump[N][K], h[N], n, p[N], w[N];
int merge(int i, int j) { return h[i] < h[j] ? i : j; }
int query(int l, int r) {
    int j = 31 - __builtin_clz(r - l + 1);
    return merge(jump[l][j], jump[r - (1 << j) + 1][j]);
}

void rec(int l, int r) {
    if(l > r) return;
    int i = query(l, r);
    int canh = h[i] * (h[i] + 1) / 2 % mod;
    
    int val = (p[i] - (l ? p[l - 1] : 0)) % mod;
    val *= (p[r] - p[i]) % mod;
    val %= mod;
    if(i > l) {
        val += (p[i - 1] % mod - (l ? p[l - 1] : 0) % mod + mod) % mod * w[i] % mod;
    }
    val += w[i] * (w[i] + 1) / 2 % mod;
    val %= mod;
    ans += val * canh % mod;
    ans %= mod;
    rec(l, i - 1);
    rec(i + 1, r);
}

void solve() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> h[i];
        jump[i][0] = i;
    }
    for(int i = 0; i < n; ++i) {
        cin >> w[i];
        p[i] = w[i] + (i ? p[i - 1] : 0);
    }
    for(int j = 1; j < K; ++j) {
        for(int i = 0; i + (1 << j) <= n; ++i) {
            jump[i][j] = merge(jump[i][j - 1], jump[i + (1 << (j - 1))][j - 1]);
        }
    }
    rec(0, n - 1);
    cout << ans << "\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

• 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