oj.uz

Submission #98544

# Submission time Handle Problem Language Result Execution time Memory
98544 2019-02-23T22:34:19 Z luciocf Vudu (COCI15_vudu) C++14
140 / 140
 931 ms 62932 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 896 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 931 ms 60944 KB Output is correct
5 Correct 326 ms 34552 KB Output is correct
6 Correct 563 ms 54108 KB Output is correct
7 Correct 561 ms 56184 KB Output is correct
8 Correct 544 ms 48796 KB Output is correct
9 Correct 660 ms 62932 KB Output is correct
10 Correct 655 ms 54720 KB Output is correct