oj.uz

Submission #875364

# Submission time Handle Problem Language Result Execution time Memory
875364 2023-11-19T09:21:42 Z sleepntsheep Vudu (COCI15_vudu) C++17
140 / 140
 836 ms 27644 KB 
#include <stdio.h>
#define INLINE inline __attribute__((always_inline))

#define N 1000000

unsigned seed = 0x8ab3acb2;
unsigned rand_(void)
{
    return (seed *= 7) >> 1;
}

long long A[N+1];
int n, p, a[N], L[N+1], R[N+1], B[N+1], S[N+1], t, alloc;

INLINE void pull(int v)
{
    S[v] = 1 + S[L[v]] + S[R[v]];
}

INLINE int node(long long x)
{
    A[++alloc] = x; S[alloc] = 1; B[alloc] = rand_();
    return alloc;
}

void split(int v, int *l, int *r, int at)
{
    if (!v) { *l=*r=0; return;}
    if (S[L[v]] < at)
    {
        split(R[v], R+v, r, at - S[L[v]] - 1);
        *l = v;
    }
    else
    {
        split(L[v], l, L+v, at);
        *r = v;
    }
    pull(v);
}

void merge(int *v, int l, int r)
{
    if (!l || !r) { *v = l^r; return; }

    if (B[l] < B[r])
    {
        merge(L+r, l, L[r]);
        *v = r;
    }
    else
    {
        merge(R+l, R[l], r);
        *v = l;
    }
    pull(*v);
}

int order(int v, long long k)
{
    if (!v) return 0;
    if (A[v] < k) return S[L[v]] + 1 + order(R[v], k);
    return order(L[v], k);
}

INLINE void insert(int *v, long long k)
{
    int b4 = order(*v, k), y1, y2, y3;
    split(*v, &y1, &y2, b4);
    merge(&y3, node(k), y2);
    merge(v, y1, y3);
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", a+i);
    scanf("%d", &p);
    long long b = 0, z = 0;
    for (int i = 0; i < n; ++i)
    {
        insert(&t, -1ll*i*p + p + b);
        b += a[i];
        z += order(t, b - 1ll*i*p + 1);
    }
    printf("%lld", z);
    return 0;
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
vudu.cpp:77:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     for (int i = 0; i < n; ++i) scanf("%d", a+i);
      |                                 ~~~~~^~~~~~~~~~~
vudu.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d", &p);
      |     ~~~~~^~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8540 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 836 ms 27468 KB Output is correct
5 Correct 391 ms 22192 KB Output is correct
6 Correct 642 ms 25260 KB Output is correct
7 Correct 628 ms 25864 KB Output is correct
8 Correct 570 ms 23996 KB Output is correct
9 Correct 752 ms 27644 KB Output is correct
10 Correct 632 ms 25252 KB Output is correct