Submission #950091

#	Time	Username	Problem	Language	Result	Execution time	Memory
950091		vjudge1	Vudu (COCI15_vudu)	C++17	140 / 140	261 ms	47472 KiB

vudu

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

struct Fenw{
    vector <int> fenw;
    int n;
    Fenw(int n) : fenw(n + 1, 0), n(n) {}
    void upd(int i, int val){
        for (; i <= n; i += i & -i ){
            fenw[i] += val;
        }
    }
    int get(int i){
        int cnt = 0;
        for (; i > 0; i -= i & -i ){
            cnt += fenw[i];
        }
        return cnt;
    }
    int get(int l, int r){
        return get(r) - get(l - 1);
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector <int> a(n + 1), pf(n + 1);
    for ( int i = 1; i <= n; i++ ){
        cin >> a[i];
        pf[i] = a[i] + pf[i - 1];
    }
    int P; cin >> P;
    vector <ar<int,2>> q;
    for ( int i = 0; i <= n; i++ ){
        q.pb({pf[i] - P * i, i});
    }
    sort(all(q));
    int ans = 0;
    Fenw fn(n + 1);
    for ( auto &[val, j]: q ){
        ans += fn.get(j + 1);
        fn.upd(j + 1, 1);
    }
    cout << ans;

    cout << '\n';
}

• Subtask 1: 140 / 140