Submission #87483

#	Time	Username	Problem	Language	Result	Execution time	Memory
87483		zoooma13	Vudu (COCI15_vudu)	C++14	140 / 140	406 ms	29264 KiB

vudu

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 1000006

int N;
long long A[MAX_N];
int P;

int bit[MAX_N+55];
int query(int idx){
    int ret = 0;
    for(int i=idx+1; i; i-=(i&-i))
        ret += bit[i];
    return ret;
}
void update(int idx){
    for(int i=idx+1; i<=N+5; i+=(i&-i))
        bit[i]++;
}

int main()
{
    scanf("%d",&N);
    for(int i=1; i<=N; i++)
        scanf("%lld",&A[i]);
    scanf("%d",&P);

    vector <pair<long long ,int>> SA{{0,0}};
    for(int i=1; i<=N; i++){
        A[i] += A[i-1]-P;
        SA.push_back({A[i] ,i});
    }
    sort(SA.begin() ,SA.end());
    for(int i=0; i<=N; i++)
        A[SA[i].second] = i;

    long long ans = 0;
    for(int i=0; i<=N; i++){
        ans += query(A[i]);
        update(A[i]);
    }

    cout << ans << endl;
}

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
vudu.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&A[i]);
         ~~~~~^~~~~~~~~~~~~~
vudu.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&P);
     ~~~~~^~~~~~~~~

• Subtask 1: 140 / 140