Submission #884750

#	Time	Username	Problem	Language	Result	Execution time	Memory
884750		Shayan86	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	44 ms	9860 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

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

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 2e5 + 50;
const ll Mod = 1e9 + 7;

ll n, h[N], w[N], pre[N], L[N], R[N], inv2;

vector<int> jahat, vv;

ll power(ll a, ll b, ll md = Mod){
    ll ans = 1;
    for(; b; b /= 2, a = a * a % md){
        if(b % 2) ans = ans * a % md;
    }
    return ans;
}

ll c2(ll x){
    return x % Mod * ((x+Mod-1) % Mod) % Mod * inv2 % Mod;
}

bool cmp(int i, int j){
    return (Mp(h[i], i) < Mp(h[j], j));
}

int main(){
    fast_io;

    inv2 = power(2, Mod-2);

    cin >> n;

    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++){
        cin >> w[i]; pre[i] = pre[i-1] + w[i];
    }

    vector<int> vec; vec.pb(0);
    for(int i = 1; i <= n; i++){
        while(h[vec.back()] >= h[i]) vec.pop_back();
        L[i] = vec.back(); vec.pb(i);
    }

    vec.clear(); vec.pb(n+1);
    for(int i = n; i > 0; i--){
        while(h[vec.back()] >= h[i]) vec.pop_back();
        R[i] = vec.back(); vec.pb(i);
    }

    for(int i = 1; i <= n; i++) jahat.pb(i);
    sort(all(jahat), cmp);

    vv.pb(jahat[0]);
    for(int i = 1; i < n; i++) if(h[jahat[i-1]] != h[jahat[i]] || L[jahat[i-1]] != L[jahat[i]]) vv.pb(jahat[i]);

    ll res = 0;
    for(int i: vv){
        ll mx = max(h[L[i]], h[R[i]]);
        ll th1 = (h[i] - mx) * mx + (h[i] - mx) + c2(h[i] - mx); th1 %= Mod;
        ll th2 = c2(pre[R[i]-1] - pre[L[i]]) + pre[R[i]-1] - pre[L[i]]; th2 %= Mod;
        res = (res + th1 * th2) % Mod;
    }

    cout << res;

}

• 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