oj.uz

Submission #961680

# Submission time Handle Problem Language Result Execution time Memory
961680 2024-04-12T10:11:14 Z Blagoj Vudu (COCI15_vudu) C++17
0 / 140
 276 ms 33588 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 = 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 (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
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8540 KB Output isn't correct
2 Incorrect 3 ms 8344 KB Output isn't correct
3 Incorrect 3 ms 8536 KB Output isn't correct
4 Incorrect 276 ms 33588 KB Output isn't correct
5 Incorrect 146 ms 26764 KB Output isn't correct
6 Incorrect 223 ms 31428 KB Output isn't correct
7 Incorrect 227 ms 30604 KB Output isn't correct
8 Incorrect 196 ms 29380 KB Output isn't correct
9 Incorrect 273 ms 32684 KB Output isn't correct
10 Incorrect 220 ms 30740 KB Output isn't correct