oj.uz

Submission #444183

# Submission time Handle Problem Language Result Execution time Memory
444183 2021-07-13T09:44:32 Z blue Vudu (COCI15_vudu) C++17
140 / 140
 323 ms 29508 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 456 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 281 ms 28536 KB Output is correct
5 Correct 180 ms 16192 KB Output is correct
6 Correct 249 ms 25236 KB Output is correct
7 Correct 249 ms 26424 KB Output is correct
8 Correct 249 ms 22784 KB Output is correct
9 Correct 323 ms 29508 KB Output is correct
10 Correct 245 ms 25640 KB Output is correct