oj.uz

Submission #40835

# Submission time Handle Problem Language Result Execution time Memory
40835 2018-02-08T18:30:52 Z Hassoony Vudu (COCI15_vudu) C++14
56 / 140
 1000 ms 65536 KB 
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef double D;
const ll inf=(1ll<<61);
const int mod=1e9+7;
const int MX=1e6+9;
int n,bit[MX];
ll a[MX],p,prf[MX];
map<ll,int>hashy;
void add(int x){
    while(x<MX){
        bit[x]++;
        x+=x&-x;
    }
}
int get(int x){
    int ret=0;
    while(x){
        ret+=bit[x];
        x-=x&-x;
    }
    return ret;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    scanf("%lld",&p);
    for(int i=1;i<=n;i++){
        a[i]-=p;
        prf[i]+=a[i]+prf[i-1];
        hashy[prf[i]]=1;
    }
    hashy[0]=1;
    int tt=0;
    for(auto pp:hashy){
        hashy[pp.first]=++tt;
    }
   // cout<<hashy[0]<<endl;

    add(hashy[0]);
    ll ans=0;
    for(int i=1;i<=n;i++){
        prf[i]=hashy[prf[i]];
  //      cout<<prf[i]<<" ";
        ans+=get(prf[i]);
        add(prf[i]);
    }
//    cout<<endl;
    cout<<ans<<endl;
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:27:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
vudu.cpp:29:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a[i]);
                            ^
vudu.cpp:31:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&p);
                     ^

Subtask #1
56.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 888 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 1040 KB Output is correct
4 Execution timed out 1097 ms 65536 KB Time limit exceeded
5 Correct 718 ms 65536 KB Output is correct
6 Execution timed out 1036 ms 65536 KB Time limit exceeded
7 Execution timed out 1020 ms 65536 KB Time limit exceeded
8 Execution timed out 1041 ms 65536 KB Time limit exceeded
9 Execution timed out 1058 ms 65536 KB Time limit exceeded
10 Execution timed out 1039 ms 65536 KB Time limit exceeded