oj.uz

Submission #950091

# Submission time Handle Problem Language Result Execution time Memory
950091 2024-03-20T05:12:51 Z vjudge1 Vudu (COCI15_vudu) C++17
140 / 140
 261 ms 47472 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 1 ms 576 KB Output is correct
4 Correct 261 ms 45492 KB Output is correct
5 Correct 132 ms 31140 KB Output is correct
6 Correct 215 ms 41248 KB Output is correct
7 Correct 218 ms 43648 KB Output is correct
8 Correct 210 ms 36980 KB Output is correct
9 Correct 252 ms 47472 KB Output is correct
10 Correct 248 ms 41024 KB Output is correct