Submission #961683

#	Time	Username	Problem	Language	Result	Execution time	Memory
961683		Blagoj	Vudu (COCI15_vudu)	C++17	140 / 140	261 ms	34088 KiB

vudu

#include <bits/stdc++.h>
 
using namespace std;
 
#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()
 
struct FenwickTree {
    vector<ll> fwt;
 
    FenwickTree(int sz) {
        fwt.resize(sz + 10000);
    }
 
    ll get(int ind) {
        ll ans = 0;
        for (ind++; ind; ind -= ind & -ind) ans += fwt[ind];
        return ans;
    }
 
    void update(int ind) {
        for (ind++; ind < fwt.size(); ind += ind & -ind) fwt[ind]++;
    }
} fwt(1e6);
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, p;
    cin >> n;
    ll a[n + 1], prf[n + 1];
    memset(prf, 0, sizeof(prf));
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prf[i] = prf[i - 1] + a[i];
    }
    cin >> p;
    vector<ll> v;
    for (ll i = 0; i <= n; i++) v.push_back({prf[i] - p * i});
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    ll ans = 0;
    for (ll i = 0; i <= n; i++) {
        ll x = lower_bound(all(v), prf[i] - p * i) - v.begin();
        ans += fwt.get(x);
        fwt.update(x);
    }
    cout << ans;
}

Compilation message (stderr)

vudu.cpp: In member function 'void FenwickTree::update(int)':
vudu.cpp:23:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for (ind++; ind < fwt.size(); ind += ind & -ind) fwt[ind]++;
      |                     ~~~~^~~~~~~~~~~~

• Subtask 1: 140 / 140