Submission #1188092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188092		peteza	Vudu (COCI15_vudu)	C++20	140 / 140	128 ms	16020 KiB

vudu

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll n;
ll qs[1000005], temp[10000005], k;
ll inv = 0;

void mg(int l, int r) {
    if(l == r) return ;
    int mid = (l+r) >> 1;
    mg(l, mid); mg(mid+1, r);
    int p1 = l, p2 = mid+1;
    for(int i=l;i<=r;i++) {
        if(p1 == mid+1) temp[i] = qs[p2++];
        else if(p2 == r+1) {
            //inv += mid+1-p1;
            temp[i] = qs[p1++];
        } else {
            if(qs[p1] <= qs[p2]) temp[i] = qs[p1++];
            else {
                inv += mid + 1 - p1;
                temp[i] = qs[p2++];
            }
        }
    }
    for(int i=l;i<=r;i++) qs[i] = temp[i];
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<=n;i++) {
        cin >> qs[i];
    }
    cin >> k;
    for(int i=1;i<=n;i++) {
        qs[i] += qs[i-1] - k;
    }
    mg(0, n);
    cout << (n*(n+1))/2 - inv;
}

• Subtask 1: 140 / 140