Submission #1236704

#TimeUsernameProblemLanguageResultExecution timeMemory
1236704neisennVudu (COCI15_vudu)C++20
140 / 140
229 ms27744 KiB
#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>;

struct BIT {
    int n;
    vector<int> f;
    void init(int _n){
        n = _n;
        f.resize(n+1, 0);
    }
    void update(int i, int v=1) {
        for (; i <= n; i += i & -i) f[i] += v;
    }
    int query(int i) const {
        int s = 0;
        for (; i > 0; i -= i & -i) s += f[i];
        return s;
    }
};

void solve(){
    int n; cin >> n;
    ll a[n+1];
    vector<ll> pref(n+1, 0);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    ll p; cin >> p;
    for (int i = 1; i <= n; i++){
        a[i] -= p;
        pref[i] = pref[i-1]+a[i];
    }
    vector<ll> val = pref;
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    auto get = [&](ll x){
        return int(lower_bound(val.begin(), val.end(), x)-val.begin())+1;
    };
    BIT bit;
    bit.init(val.size());
    ll ans = 0;
    for (int i = 0; i <= n; i++){
        int id = get(pref[i]);
        ans += bit.query(id);
        bit.update(id);
    }
    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();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...