Submission #866715

#	Time	Username	Problem	Language	Result	Execution time	Memory
866715		Lalic	Fancy Fence (CEOI20_fancyfence)	C++17	30 / 100	24 ms	4724 KiB

fancyfence

#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 last=0;
    for(int i=0;i<n;i++)
        cin >> arr[i].fi;
    for(int i=0;i<n;i++){
        arr[i].se.fi=last;

        ll x; cin >> x;
        last+=x;

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

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

    sort(all(arr));

    last=0;
    ll ans=0;
    for(int i=0;i<n;i++){
        auto aux=st.upper_bound({{arr[i].se.fi, -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;
}

• 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