Submission #444183

#	Time	Username	Problem	Language	Result	Execution time	Memory
444183		blue	Vudu (COCI15_vudu)	C++17	140 / 140	323 ms	29508 KiB

vudu

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long* a;

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

    int N;
    cin >> N;

    a = new long long[N+1];
    a[0] = 0;
    for(int i = 1; i <= N; i++) cin >> a[i];

    long long P;
    cin >> P;
    for(int i = 1; i <= N; i++)
    {
        a[i] = a[i-1] + (a[i] - P);
    }

    //Count number of (i, j) such that i < j and a[i] < a[j]

    int I[N+1];
    for(int i = 0; i <= N; i++) I[i] = i;
    sort(I, I+N+1, [] (int x, int y)
    {
        if(a[x] == a[y]) return x < y;
        else return a[x] < a[y];
    });

    vector<long long> BIT(2+N, 0);
    long long res = 0;
    for(int i:I)
    {
        for(int j = (i+1)-1; j >= 0+1; j -= j&-j)
            res += BIT[j];

        for(int j = (i+1); j <= N+1; j += j&-j)
            BIT[j] += 1;
    }

    cout << res << '\n';
}

• Subtask 1: 140 / 140