oj.uz

Submission #81589

# Submission time Handle Problem Language Result Execution time Memory
81589 2018-10-25T13:08:00 Z chelly Vudu (COCI15_vudu) C++11
140 / 140
 438 ms 21008 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 5 ms 532 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 438 ms 20492 KB Output is correct
5 Correct 232 ms 20492 KB Output is correct
6 Correct 368 ms 20492 KB Output is correct
7 Correct 377 ms 20492 KB Output is correct
8 Correct 326 ms 20492 KB Output is correct
9 Correct 435 ms 21008 KB Output is correct
10 Correct 391 ms 21008 KB Output is correct