Submission #252694

#	Time	Username	Problem	Language	Result	Execution time	Memory
252694		VEGAnn	Vudu (COCI15_vudu)	C++14	140 / 140	401 ms	33616 KiB

vudu

#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 / 140