Submission #1088260

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1088260	2024-09-14T07:23:51 Z	nguyen31hoang08minh2003	Vudu (COCI15_vudu)	C++17	140 / 140	240 ms	33460 KB

vudu

#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

struct FenwickTree {
    int n;
    vi bit;
    void resize(int newN) {
        n = newN;
        bit.resize(n + 1);
    }
    void update(int x, int val) {
        for (; x <= n; x += x & -x)
            bit[x] += val;
    };
    int query(int x) const {
        int res = 0;
        for (; x > 0; x -= x & -x)
            res += bit[x];
        return res;
    }
};

/*
    (a[l] + ... + a[r]) / (r - l + 1) >= p
     a[l] + ... + a[r]                >= p * (r - l + 1)
     (a[l] - p) + ... + (a[r] - p)    >= 0
    prefix[r] - prefix[l - 1]         >= 0
    prefix[r]                         >= prefix[l - 1]
*/

const int maxN = 1000005;

int n, p, a[maxN];
ll prefix[maxN];

void Input() {
    cin >> n;
    fort(i, 1, n)
        cin >> a[i];
    cin >> p;
}

void Solve() {
    vector<ll> h(1, 0);
    FenwickTree bit;
    ll res = 0;
    fort(i, 1, n) {
        prefix[i] = prefix[i - 1] + a[i] - p;
        h.pb(prefix[i]);
    }
    sort(all(h));
    h.erase(unique(all(h)), h.end());
    bit.resize(h.size());
    bit.update((lower_bound(all(h), 0) - h.begin()) + 1, 1);
    for (int i = 1, j; i <= n; ++i) {
        j = (lower_bound(all(h), prefix[i]) - h.begin()) + 1;
        res += bit.query(j);
        bit.update(j, 1);
    }
    cout << res << '\n';
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solve();
    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	604 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	1 ms	512 KB	Output is correct
4	Correct	232 ms	32432 KB	Output is correct
5	Correct	127 ms	20164 KB	Output is correct
6	Correct	203 ms	28576 KB	Output is correct
7	Correct	201 ms	29872 KB	Output is correct
8	Correct	192 ms	25860 KB	Output is correct
9	Correct	238 ms	33460 KB	Output is correct
10	Correct	240 ms	29100 KB	Output is correct