Submission #1230257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230257		lechaa	Vudu (COCI15_vudu)	C++20	140 / 140	560 ms	55144 KiB

vudu

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

void update(int i, int l, int r, int i1){
    if(l == r){
        t[i]++;
        return;
    }
    int mid = (l+r)/2;
    if(i1 <= mid){
        update(i*2, l, mid, i1);
    }else{
        update(i*2+1, mid+1, r, i1);
    }
    t[i] = t[i*2] + t[i*2+1];
}

int query(int i, int l, int r, int l1, int r1){
    if(l > r1 || l1 > r) return 0;
    if(l1 <= l && r1 >= r){
        return t[i];
    }
    int mid = (l+r)/2;
    return query(i*2, l, mid, l1, r1) + query(i*2+1, mid+1, r, l1, r1);
}

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    vector<int> x(n);
    for(int i = 0; i < n; i++){
        cin >> x[i];
    }
    int k; cin >> k;
    for(int i = 0; i < n; i++){
        x[i] -= k;
    }
    vector<long long> pref(n+1);
    ll sum = 0;
    for(int i = 1; i <= n; i++){
        sum += x[i-1];
        pref[i] = sum;
    }
    vector<long long> j = pref;
    sort(j.begin(), j.end());
    j.erase(unique(j.begin(), j.end()), j.end());
    t.resize(j.size()*4);
    sum = 0;
    auto it = lower_bound(j.begin(), j.end(), 0);
    update(1, 0, j.size()-1, it - j.begin());
    for(int i = 0; i < n; i++){
        auto it = lower_bound(j.begin(), j.end(), pref[i+1]);
        int idx = (it - j.begin());
        sum += query(1, 0, j.size()-1, 0, idx);
        update(1, 0, j.size()-1, idx);
    }
    cout << sum << "\n";
    return 0;
}

Compilation message (stderr)

vudu.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main(){
      | ^~~~

• Subtask 1: 140 / 140