Submission #623672

#	Time	Username	Problem	Language	Result	Execution time	Memory
623672		Vladth11	Fancy Fence (CEOI20_fancyfence)	C++14	30 / 100	37 ms	9980 KiB

fancyfence

#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() {
    //ifstream cin(".in");
    //ofstream cout(".out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, i;
    ll total = 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(avem, stiva[vf].second);
            vf--;
        }
        stiva[++vf] = {h[i], avem};
    }
    vf = 0;
    for(i = n; i >= 1; i--){
        ll avem = w[i];
        while(vf && stiva[vf].first >= h[i]){
            add(total, combined(h[i], stiva[vf].second, w[i]));
            add(avem, stiva[vf].second);
            vf--;
        }
        stiva[++vf] = {h[i], avem};
    }
    for(i = 1; i <= n; i++){
        add(total, -combined(h[i], mp[h[i]], w[i]));
        add(mp[h[i]], w[i]);
    }
    //debug(total);
    cout << total;
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27