Submission #623693

#TimeUsernameProblemLanguageResultExecution timeMemory
623693Vladth11Fancy Fence (CEOI20_fancyfence)C++14
100 / 100
25 ms5352 KiB
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 100001;
const ll VMAX = 101;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 117;
const ll nr_of_bits = 18;
const ll inv2 = 500000004;

pii stiva[NMAX];
ll vf;
ll scor = 0;
ll h[NMAX];
ll w[NMAX];

ll lgput(ll n, ll p){
    ll rez = 1;
    while(p){
        if(p % 2){
            rez = (1LL * rez * n) % MOD;
        }
        n = (1LL * n * n) % MOD;
        p /= 2;
    }
    return rez;
}

ll gauss(ll x){
    return 1LL * (1LL * x * (x + 1)) % MOD * inv2 % MOD;
}

ll cate(ll h, ll w){
    return (1LL * gauss(h) * gauss(w)) % MOD;
}

ll combined(ll h, ll w1, ll w2){
    return (1LL * (1LL * gauss(h) * w1) % MOD * w2) % MOD;
}

void add(ll &x, ll val){
    x += val;
    if(x >= MOD){
        x -= MOD;
    }
    if(x < 0){
        x += MOD;
    }
}

unordered_map <int, ll> mp;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, i;
    ll total = 0, scor = 0;
    cin >> n;
    for(i = 1; i <= n; i++) cin >> h[i];
    for(i = 1; i <= n; i++) cin >> w[i];
    for(i = 1; i <= n; i++){
        add(total, cate(h[i], w[i]));
        ll avem = w[i];
        while(vf && stiva[vf].first >= h[i]){
            add(total, combined(h[i], stiva[vf].second, w[i]));
            add(scor, -(gauss(stiva[vf].first) * stiva[vf].second) % MOD);
            add(avem, stiva[vf].second);
            vf--;
        }
        add(total, (scor * w[i]) % MOD);
        stiva[++vf] = {h[i], avem};
        add(scor, (gauss(stiva[vf].first) * stiva[vf].second) % MOD);
    }
    cout << total;
    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...