oj.uz

Submission #866715

# Submission time Handle Problem Language Result Execution time Memory
866715 2023-10-26T20:38:07 Z Lalic Fancy Fence (CEOI20_fancyfence) C++17
30 / 100
 24 ms 4724 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 11 ms 2528 KB Output is correct
4 Correct 22 ms 4700 KB Output is correct
5 Correct 23 ms 4700 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 856 KB Output is correct
4 Correct 11 ms 2396 KB Output is correct
5 Correct 23 ms 4724 KB Output is correct
6 Correct 24 ms 4700 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 12 ms 2396 KB Output is correct
10 Correct 22 ms 4444 KB Output is correct
11 Correct 21 ms 4596 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -