oj.uz

Submission #252723

# Submission time Handle Problem Language Result Execution time Memory
252723 2020-07-26T07:46:13 Z NONAME Vudu (COCI15_vudu) C++14
140 / 140
 394 ms 31792 KB 
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;

const int N = int(1e6) + 10;

int n;
ll a[N], pf[N], p, fen[N];
vector <ll> vec;

ll sum(int x) { ll res = 0; while (x >= 0) res += fen[x], x = (x & (x + 1)) - 1; return res; }
void upd(int x) { while (x < int(vec.size())) ++fen[x], x = (x | (x + 1)); }

int main() {
    fast_io;

    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cin >> p;

    for (int i = 0; i < n; ++i)
        pf[i] = (i - 1 < 0 ? 0 : pf[i - 1]) + a[i];

    vec.push_back(0);
    for (int i = 0; i < n; ++i) {
        ll vl = pf[i] - p * (i + 1);

        vec.push_back(vl);
    }

    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());

    //for (int i = 0; i < int(vec.size()); ++i)
        //cerr << vec[i] << " ";
    //cerr << "\n";

    upd(lower_bound(vec.begin(), vec.end(), 0ll) - vec.begin());
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        int ps = lower_bound(vec.begin(), vec.end(), pf[i] - p * (i + 1)) - vec.begin();
        //cerr << ps << "\n";

        ans += sum(ps);
        upd(ps);
    }

    cout << ans << "\n";
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 394 ms 30804 KB Output is correct
5 Correct 203 ms 17624 KB Output is correct
6 Correct 331 ms 27348 KB Output is correct
7 Correct 335 ms 28368 KB Output is correct
8 Correct 311 ms 24696 KB Output is correct
9 Correct 390 ms 31792 KB Output is correct
10 Correct 338 ms 27732 KB Output is correct