Submission #81587

#	Time	Username	Problem	Language	Result	Execution time	Memory
81587		chelly	Vudu (COCI15_vudu)	C++11	126 / 140	440 ms	66560 KiB

vudu

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

int N, P;
long long int ar[1000001];
int p[1000001], bit[1000002];

int query(int pos) {
    int ans = 0;
    for(int i = pos; i>0; i -= i&-i) ans += bit[i];
    return ans;
}
int update (int pos){
    for(int i = pos; i<=N+1; i += i&-i) bit[i]++;
}

bool cmp (int x, int y) {  return ar[x] < ar[y]||(ar[x]==ar[y]&&x<y); }

int main () {

    scanf("%d", &N);
    for(int i = 1; i <= N; i++) scanf("%lld", ar + i);

    scanf("%d", &P);
    for(int i = 1; i <= N; i++)
        ar[i] += ar[i-1] - P;

    for(int i = 0; i <= N; i++)
        p[i] = i;
    sort(p, p + N + 1, cmp);

    long long int ans = 0;
    for(int i = 0; i <= N; i++){
        ans += query(p[i] + 1);
        update (p[i]+1);
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

vudu.cpp: In function 'int update(int)':
vudu.cpp:15:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
vudu.cpp: In function 'int main()':
vudu.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
vudu.cpp:22:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= N; i++) scanf("%lld", ar + i);
                                 ~~~~~^~~~~~~~~~~~~~~~
vudu.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &P);
     ~~~~~^~~~~~~~~~

• Subtask 1: 126 / 140