oj.uz

Submission #252694

# Submission time Handle Problem Language Result Execution time Memory
252694 2020-07-26T06:48:39 Z VEGAnn Vudu (COCI15_vudu) C++14
140 / 140
 401 ms 33616 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 1000100;
vector<ll> vc;
int n, a[N], p, fen[N];
ll pf[N], ans = 0;

void update(int x){
    for (; x < sz(vc); x = (x | (x + 1)))
        fen[x]++;
}

int sum(int x){
    int res = 0;
    for (; x >= 0; x = (x & (x + 1)) - 1)
        res += fen[x];
    return res;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

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

    cin >> p;

    pf[0] = 0;

    vc.PB(0);

    for (int i = 1; i <= n; i++){
        pf[i] = pf[i - 1] + ll(a[i]) - ll(p);

        vc.PB(pf[i]);
    }

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    update(lower_bound(all(vc), pf[0]) - vc.begin());

    for (int i = 1; i <= n; i++){
        int ps = lower_bound(all(vc), pf[i]) - vc.begin();

        ans += sum(ps);

        update(ps);
    }

    cout << ans;

    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 373 ms 32800 KB Output is correct
5 Correct 213 ms 20200 KB Output is correct
6 Correct 331 ms 28884 KB Output is correct
7 Correct 341 ms 30040 KB Output is correct
8 Correct 302 ms 26068 KB Output is correct
9 Correct 401 ms 33616 KB Output is correct
10 Correct 337 ms 29268 KB Output is correct