Submission #923505

#	Time	Username	Problem	Language	Result	Execution time	Memory
923505		Art_ogo	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	81 ms	10200 KiB

fancyfence

#include <bits/stdc++.h>

#define ve vector
#define ld long double
#define ll long long
#define all(x) x.begin(), x.end()
#define fi first
#define se second

using namespace std;
using namespace chrono;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#pragma GCC optimize("Ofast")

const int MAXN = 1e5+10;
const ll mod = 1e9+7;

struct rect{
    ll h, w, id;
};

inline bool comp(const rect& r1, const rect& r2){
    return r1.h < r2.h;
}

rect v[MAXN];
ll pref[MAXN];

int n;

ll binpow(ll a, ll n){
    if(n == 0)
        return 1;
    if(n & 1)
        return (a*binpow(a, n - 1))%mod;
    ll t = binpow(a, n / 2);
    return (t*t) % mod;
}

ll f(ll w){
    ll csum = (w*(w - 1)+mod)%mod;
    csum = (csum*binpow(2, mod - 2)) % mod;
    csum = (csum + w) % mod;
    return csum;
}

void solve(){
    cin >> n; 
    set<int> del;
    for(int i = 1; i <= n; i++)
        cin >> v[i].h;
    for(int i = 1; i <= n; i++)
        cin >> v[i].w;
    for(int i = 1; i <= n; i++)
        v[i].id = i;
    for(int i = 1; i <= n; i++)
        pref[i] = (pref[i - 1] + v[i].w) % mod;
    sort(v + 1, v + 1 + n, comp);
    ll res = 0;
    ll w = (pref[n] - pref[0] + mod) % mod;
    ll csum = f(w);
    for(int i = 1; i <= n; i++){
        auto it = del.lower_bound(v[i].id);
        ll l, r;
        if(it == del.end())
            r = n;
        else r = *it - 1;
        if(it == del.begin())
            l = 0;
        else
            l = *prev(it);
        
        ll ph;
        if(i == 1)
            ph = 0;
        else ph = v[i - 1].h;
        ll sum = ((ph + 1)+v[i].h) % mod;
        sum = (sum*(v[i].h - ph) + mod)%mod;
        sum = (sum*binpow(2, mod - 2)) % mod;
        ll pr = (csum*sum) % mod;
        res = (res + pr) % mod;
        del.insert(v[i].id);
        w = (pref[r] - pref[l] + mod) % mod;
        csum = (csum - f(w) + mod) % mod;
        w = (pref[v[i].id - 1] - pref[l] + mod) % mod;
        csum = (csum + f(w)) % mod;
        w = (pref[r] - pref[v[i].id] + mod) % mod;
        csum = (csum + f(w)) % mod;
    }
    cout << res;
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.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