Submission #98544

#	Time	Username	Problem	Language	Result	Execution time	Memory
98544		luciocf	Vudu (COCI15_vudu)	C++14	140 / 140	931 ms	62932 KiB

vudu

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
 
using namespace std;
 
const int maxn = 1e6+10;
 
typedef int_fast64_t ll;

typedef int_fast32_t ii;
 
struct node
{
    node *l, *r;
    ll v;
    ii w, sz;
 
    node(ll vv)
    {
        l = r = NULL;
        v = vv, sz = 1, w = rand();
    }
};
 
typedef node*& node_t;
 
ii sz(node *t)
{
    return (t ? t->sz : 0);
}
 
void op(node *t)
{
    if (t) t->sz = sz(t->l)+sz(t->r)+1;
}
 
void split(node *t, node_t l, node_t r, ll x)
{
    if (!t) return void(l=r=NULL);
 
    if (t->v > x) split(t->l, l, t->l, x), r = t;
    else split(t->r, t->r, r, x), l = t;
 
    op(t);
}
 
void insert(node_t t, node *it)
{
    if (!t) t = it;
    else if (it->w > t->w) split(t, it->l, it->r, it->v), t = it;
    else insert((it->v > t->v ? t->r : t->l), it);
 
    op(t);
}
 
ii query(node *t, ll x)
{
    if (!t) return 0;
    else if (t->v > x) return sz(t->r)+1+query(t->l, x);
    return query(t->r, x);
}
 
ii num[maxn];
 
ll soma[maxn];
 
#define gc getchar_unlocked
inline int scan(){
    ii n=0, x=gc();
    for(;x<'0'||x>'9';x=gc()){}
    for(;!(x<'0'||x>'9');x=gc()) n = 10*n + x-'0';
    return n;
}
 
int main(void)
{
    ii n, p;
    n = scan();
 
    for (ii i = 1; i <= n; i++)
        num[i] = scan();
 
    p = scan();
 
    soma[0] = -p;
    for (ii i = 1; i <= n; i++)
        soma[i] = soma[i-1]+(ll)num[i]-(ll)p;
 
    ll ans = 0LL;
    node *t = NULL;
    
    node *it = new node(soma[0]);
    insert(t, it);
 
    for (ii i = 1; i <= n; i++)
    {
        ans += (ll)i-(ll)query(t, soma[i]);
 
        it = new node(soma[i]);
        insert(t, it);
    }
 
    cout << ans << '\n';
}

• Subtask 1: 140 / 140