oj.uz

Submission #875368

# Submission time Handle Problem Language Result Execution time Memory
875368 2023-11-19T09:25:38 Z sleepntsheep Vudu (COCI15_vudu) C
140 / 140
 775 ms 27792 KB 
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define INLINE inline __attribute__((always_inline))
#define N 1000000

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")

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 4 ms 6488 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 775 ms 27072 KB Output is correct
5 Correct 367 ms 22268 KB Output is correct
6 Correct 645 ms 25068 KB Output is correct
7 Correct 600 ms 25748 KB Output is correct
8 Correct 557 ms 23996 KB Output is correct
9 Correct 714 ms 27792 KB Output is correct
10 Correct 652 ms 25352 KB Output is correct