Submission #875042

#	Time	Username	Problem	Language	Result	Execution time	Memory
875042		teo_thrash	Vudu (COCI15_vudu)	C++14	140 / 140	931 ms	35316 KiB

vudu

#include <iostream>
#include <cassert>
#include <random>
using namespace std;
 
typedef long long ll;
const int maxn = 1e6+3;
int a[maxn];
 
int root, NODE;
ll val[maxn+1];
int sz[maxn+1];
int prior[maxn+1];
int lft[maxn+1];
int rght[maxn+1];
 
void recalc(int t) {
    sz[t] = sz[lft[t]] + sz[rght[t]] + 1;
}
 
void split(int t, ll x, int &tl, int &tr) {
    if (!t) {
        tl = tr = 0;
        return;
    }
    if (val[t] <= x) {
        split(rght[t], x, tl, tr);
        rght[t] = tl;
        tl = t;
    } else {
        split(lft[t], x, tl, tr);
        lft[t] = tr;
        tr = t;
    }
    recalc(t);
}
 
int mrg(int t1, int t2) {
    if (!t1 || !t2) return t1? t1: t2;
    if (prior[t1] < prior[t2]) swap(t1, t2);
    if (val[t2] <= val[t1]) {
        lft[t1] = mrg(lft[t1], t2);
    } else {
        rght[t1] = mrg(rght[t1], t2);
    }
    recalc(t1);
    assert(t1 >= 0);
    return t1;
}
 
void insrt(ll x) {
    ++NODE;
    sz[NODE] = 1;
    val[NODE] = x;
    prior[NODE] = rand();
    if (!root) {
        root = NODE;
    } else {
        int tl, tr;
        split(root, x, tl, tr);
        root = mrg(mrg(tl, NODE), tr);
    }
}
 
int count_lte(ll x) {
    int tl, tr;
    split(root, x, tl, tr);
    int ans = sz[tl];
    root = mrg(tl, tr);
 
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  	
  	int n, k;
  	cin>>n;
 
    for (int i=0; i<n; ++i) cin>>a[i];
  	cin>>k;
 
    ll prefsum = 0;
    ll ans = 0;
    insrt(0);
    for (int i=0; i<n; ++i) {
        prefsum += a[i]-k;
        ans += count_lte(prefsum);
        insrt(prefsum);
    }
 
    cout << ans << endl;
}

• Subtask 1: 140 / 140