oj.uz

Submission #961683

# Submission time Handle Problem Language Result Execution time Memory
961683 2024-04-12T10:13:15 Z Blagoj Vudu (COCI15_vudu) C++17
140 / 140
 261 ms 34088 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 3 ms 8536 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 261 ms 32996 KB Output is correct
5 Correct 134 ms 25032 KB Output is correct
6 Correct 226 ms 30408 KB Output is correct
7 Correct 217 ms 31872 KB Output is correct
8 Correct 200 ms 29040 KB Output is correct
9 Correct 256 ms 34088 KB Output is correct
10 Correct 220 ms 31528 KB Output is correct