Submission #866716

#TimeUsernameProblemLanguageResultExecution timeMemory
866716LalicFancy Fence (CEOI20_fancyfence)C++17
100 / 100
57 ms6252 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1e5+10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9+7;
const ll inv2 = 500000004;

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

void solve(){
    int n; cin >> n;

    vector<pair<ll, pll>> arr(n);
    ll id=0;
    for(int i=0;i<n;i++)
        cin >> arr[i].fi;
    for(int i=0;i<n;i++){
        arr[i].se.fi=id;

        ll x; cin >> x;
        id+=x;

        arr[i].se.se=id;
    }

    set<pair<pll, ll>> st;
    st.insert({{0, arr[n-1].se.se}, 0});

    sort(all(arr));

    ll ans=0;
    for(int i=0;i<n;i++){
        auto aux=st.upper_bound({{arr[i].se.fi+1, -1}, -1});
        aux--;

        pair<pll, ll> curr=*aux;
        st.erase(aux);

        ans+=(((gauss((arr[i].fi)%MOD)-gauss((curr.se)%MOD)+MOD)%MOD)*gauss((curr.fi.se-curr.fi.fi)%MOD))%MOD;
        ans%=MOD;

        if(arr[i].se.fi!=curr.fi.fi)
            st.insert({{curr.fi.fi, arr[i].se.fi}, arr[i].fi});
        if(arr[i].se.se!=curr.fi.se)
            st.insert({{arr[i].se.se, curr.fi.se}, arr[i].fi});
    }

    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    // freopen("fetiera.in", "r", stdin);

    int tt=1;
    // cin >> tt;
    while(tt--)
        solve();
    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...