Submission #1230195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230195		lechaa	Vudu (COCI15_vudu)	C++20	98 / 140	633 ms	74568 KiB

vudu

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef __gnu_pbds::tree<pair<long long, long long>, __gnu_pbds::null_type, less<pair<long long, long long>>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;

int 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;
    }
    sum = 0;
    ordered_set o;
    o.insert({0, -1});
    for(int i = 0; i < n; i++){
        sum += o.order_of_key({pref[i+1], 1e9});
        // cout << o.order_of_key({pref[i+1], i}) << " ";
        o.insert({pref[i+1], i});
    }
    cout << sum << "\n";
    return 0;
}

/*
2
-1 1 0

-1 0 0

misal skrng 5

*/

• Subtask 1: 98 / 140