제출 #875364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
875364		sleepntsheep	Vudu (COCI15_vudu)	C++17	140 / 140	836 ms	27644 KiB

vudu

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 140