Submission #1236671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236671		neisenn	Vudu (COCI15_vudu)	C++20	56 / 140	1038 ms	86476 KiB

vudu

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const char nl = '\n';
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void solve(){
    int n; cin >> n;
    ll a[n+1], b[n+1], pref[n+1];
    pref[0] = 0;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    ll p; cin >> p;
    oset<pli> s;
    for (int i = 1; i <= n; i++){
        b[i] = a[i]-p;
        pref[i] = pref[i-1]+b[i];
        s.insert({pref[i], i});
    }
    ll sum = 0, ans = 0;
    for (int i = 1; i <= n+1; i++){
        // cout << sum << nl;
        ll x = s.order_of_key({sum, 0});
        // cout << s.size() << ' ' << x << ' ' << i << nl;
        ans += s.size()-x;
        if (i > n) break;
        s.erase({pref[i], i});
        sum += b[i];
    }
    cout << ans << nl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t--){
        solve();
    }
}

• Subtask 1: 56 / 140