oj.uz

Submission #250400

# Submission time Handle Problem Language Result Execution time Memory
250400 2020-07-17T17:11:22 Z apostoldaniel854 Vudu (COCI15_vudu) C++14
140 / 140
 295 ms 28096 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int N = 1e6;

int n, p;
int aib[1 + N + 2];
int a[1 + N];
int val[1 + N];


inline int lsb (int x) {
    return x & -x;
}

int qry (int pos) {
    int ans = 0;
    while (pos) {
        ans += aib[pos];
        pos -= lsb (pos);
    }
    return ans;
}

void upd (int pos, int val) {
    while (pos <= n + 2) {
        aib[pos] += val;
        pos += lsb (pos);
    }
}

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> p;
    vector <pair <ll, int>> v;
    v.pb ({0, 0});
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        a[i] -= p;
        sum += a[i];
        v.pb ({sum, i});
    }
    sort (v.begin (), v.end ());
    int cnt = 1;
    val[v[0].second] = cnt;
    for (int i = 1; i <= n; i++) {
        if (v[i].first != v[i - 1].first)
            cnt++;
        val[v[i].second] = cnt;
    }
    ll ans = 0;
    for (int i = 0; i <= n; i++) {
        ans += qry (val[i]);
        upd (val[i], 1);
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 292 ms 27072 KB Output is correct
5 Correct 170 ms 19044 KB Output is correct
6 Correct 252 ms 23872 KB Output is correct
7 Correct 270 ms 25020 KB Output is correct
8 Correct 241 ms 21828 KB Output is correct
9 Correct 295 ms 28096 KB Output is correct
10 Correct 262 ms 24252 KB Output is correct