Submission #1276306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276306		thesen	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	45 ms	34768 KiB

fancyfence

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define vll vector<ll>
#define vbool vector<bool>
#define pairll pair<ll,ll>
#define fi first
#define sc second
#define rever greater<ll>()
using namespace std;

ll res = 0, md = 1e9+7;
vll pw(30); 
ll mn(vector<vll> &st, vll &h, ll l, ll r){
    ll lg = log2(r-l+1);
    if(h[st[lg][l]] < h[st[lg][r-pw[lg]+1]]){
        return st[lg][l];
    }else return st[lg][r-pw[lg]+1];
}

ll v(ll x){
    return ((x*(x+1)/2)%md);
}

void dnc(vll &h, vll &w, vector<vll> &st, ll l, ll r, ll k){
    if(l > r)return;
    ll mid = mn(st, h, l, r);
    if(k < h[mid]){
        ll wid = w[r];
        if(l>0)wid -= w[l-1];
        wid %= md;
        res += (v(wid)*v(h[mid]))%md;
        res %= md;
        res -= (v(wid)*v(k));
        res %= md;
        res += md;
        res %= md;
    }
    if(l==r)return;
    dnc(h, w, st, l, mid-1, h[mid]);
    dnc(h, w, st, mid+1, r, h[mid]);
}

void solve(){
    ll n; cin >> n;
    vll h(n), w(n);
    for(ll i = 0; i < n; i++) cin >> h[i];
    for(ll i = 0; i < n; i++) cin >> w[i];
    for(ll i = 1; i < n; i++) w[i]+=w[i-1];

    vector<vll> st(30, vll(n));
    pw[0]=1; for(ll i = 1; i < 30; i++)pw[i]=pw[i-1]*2;
    for(ll i = 0; i < n; i++)st[0][i] = i;
    for(ll i = 1; i < 30; i++){
        for(ll j = 0; j+pw[i]-1 < n; j++){
            if(h[st[i-1][j]] < h[st[i-1][j+pw[i-1]]]){
                st[i][j] = st[i-1][j];
            }else st[i][j] = st[i-1][j+pw[i-1]];
        }
    }
     
    dnc(h, w, st, 0, n-1, 0);
    cout << res << endl;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    ll t=1; //cin >> t;
    for(int i = 1; i <= t; i++){
        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