Submission #1236697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236697		neisenn	Vudu (COCI15_vudu)	C++20	98 / 140	475 ms	74728 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>;

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], pref[n+1];
    pref[0] = 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];
    }
    set<ll> st(pref, pref+n+1);
    vector<ll> val(st.begin(), st.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();
    }
}

• Subtask 1: 98 / 140