oj.uz

Submission #875363

# Submission time Handle Problem Language Result Execution time Memory
875363 2023-11-19T09:20:29 Z sleepntsheep Vudu (COCI15_vudu) C++17
140 / 140
 820 ms 27696 KB 
#include <stdio.h>

#define N 1000000

unsigned seed = 0x8983acb2;
unsigned rand_(void)
{
    return (seed *= 3) >> 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;

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

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);
}

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);
}

#if 0
void print(int v)
{
    if (!v) return;
    print(L[v]);
    printf(" %lld ", A[v]);
    print(R[v]);
}
#endif

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);
        //print(t); puts(""); printf("%lld\n",z);
    }
    printf("%lld", z);
    return 0;
}

Compilation message

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

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8536 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 820 ms 27184 KB Output is correct
5 Correct 402 ms 22068 KB Output is correct
6 Correct 655 ms 24988 KB Output is correct
7 Correct 649 ms 25656 KB Output is correct
8 Correct 598 ms 24000 KB Output is correct
9 Correct 791 ms 27696 KB Output is correct
10 Correct 668 ms 25492 KB Output is correct