oj.uz

Submission #961678

# Submission time Handle Problem Language Result Execution time Memory
961678 2024-04-12T10:10:08 Z Blagoj Vudu (COCI15_vudu) C++17
0 / 140
 269 ms 42852 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 + 100);
    }

    int get(int ind) {
        ll ans = 0;
        for (ind++; ind; ind -= ind & -ind) ans = max(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 (int 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 (int i = 0; i <= n; i++) {
        int 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
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8536 KB Output isn't correct
2 Incorrect 4 ms 8280 KB Output isn't correct
3 Incorrect 3 ms 8284 KB Output isn't correct
4 Incorrect 269 ms 41688 KB Output isn't correct
5 Incorrect 142 ms 31180 KB Output isn't correct
6 Incorrect 230 ms 39280 KB Output isn't correct
7 Incorrect 229 ms 40752 KB Output isn't correct
8 Incorrect 202 ms 36468 KB Output isn't correct
9 Incorrect 256 ms 42852 KB Output isn't correct
10 Incorrect 227 ms 39364 KB Output isn't correct