oj.uz

Submission #87482

# Submission time Handle Problem Language Result Execution time Memory
87482 2018-11-30T23:51:27 Z zoooma13 Vudu (COCI15_vudu) C++14
42 / 140
 1000 ms 66560 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 1000006

int N;
int a[MAX_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] += 1;
}

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

    map <long long ,int> mp;mp[0];
    for(int i=1; i<=N; i++){
        A[i] = a[i]+A[i-1]-P;
        mp[A[i]];
    }
    int id = 0;
    for(auto&i : mp)
        i.second = id++;
    for(int i=0; i<=N; i++)
        A[i] = mp[A[i]];

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

    cout << ans << endl;
}

Compilation message

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

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 888 KB Output is correct
2 Correct 5 ms 916 KB Output is correct
3 Correct 7 ms 1016 KB Output is correct
4 Runtime error 664 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 614 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.
6 Execution timed out 1070 ms 66560 KB Time limit exceeded
7 Runtime error 562 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Execution timed out 1078 ms 66560 KB Time limit exceeded
9 Runtime error 605 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Execution timed out 1066 ms 66560 KB Time limit exceeded