oj.uz

Submission #81587

# Submission time Handle Problem Language Result Execution time Memory
81587 2018-10-25T13:06:58 Z chelly Vudu (COCI15_vudu) C++11
126 / 140
 440 ms 66560 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
126.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 4 ms 540 KB Output is correct
3 Correct 4 ms 756 KB Output is correct
4 Correct 440 ms 25116 KB Output is correct
5 Correct 254 ms 25116 KB Output is correct
6 Correct 361 ms 36940 KB Output is correct
7 Correct 390 ms 46104 KB Output is correct
8 Correct 329 ms 51724 KB Output is correct
9 Correct 430 ms 65048 KB Output is correct
10 Runtime error 374 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.