Submission #875367

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
875367	2023-11-19T09:25:26 Z	sleepntsheep	Vudu (COCI15_vudu)	C	140 / 140	792 ms	27704 KB

vudu

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define INLINE inline __attribute__((always_inline))

#define N 1000000

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

int read () {
	int result = 0;
	char ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9') result = (result << 3) + (result << 1) + ch - '0', ch = getchar();
    return result;
}

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()
{
    srand(time(NULL));
    n = read();
    for (int i = 0; i < n; ++i) a[i] = read();
    p = read();
    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;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	6492 KB	Output is correct
2	Correct	3 ms	6492 KB	Output is correct
3	Correct	3 ms	6492 KB	Output is correct
4	Correct	792 ms	27132 KB	Output is correct
5	Correct	365 ms	22208 KB	Output is correct
6	Correct	635 ms	24996 KB	Output is correct
7	Correct	596 ms	25492 KB	Output is correct
8	Correct	560 ms	23960 KB	Output is correct
9	Correct	712 ms	27704 KB	Output is correct
10	Correct	610 ms	25216 KB	Output is correct