oj.uz

Submission #98542

# Submission time Handle Problem Language Result Execution time Memory
98542 2019-02-23T22:33:00 Z luciocf Vudu (COCI15_vudu) C++14
0 / 140
 913 ms 65528 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
 
using namespace std;
 
const int maxn = 1e6+10;
 
typedef uint_fast64_t ll;

typedef uint_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);
    }
 
    printf("%lud\n", ans);
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 896 KB Output isn't correct
2 Incorrect 4 ms 768 KB Output isn't correct
3 Incorrect 5 ms 768 KB Output isn't correct
4 Incorrect 913 ms 61268 KB Output isn't correct
5 Incorrect 322 ms 34988 KB Output isn't correct
6 Incorrect 652 ms 54340 KB Output isn't correct
7 Incorrect 569 ms 56552 KB Output isn't correct
8 Incorrect 581 ms 49088 KB Output isn't correct
9 Incorrect 715 ms 65528 KB Output isn't correct
10 Incorrect 623 ms 54924 KB Output isn't correct