oj.uz

Submission #40841

# Submission time Handle Problem Language Result Execution time Memory
40841 2018-02-08T18:55:10 Z Hassoony Vudu (COCI15_vudu) C++14
140 / 140
 461 ms 31072 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],p;
int a[MX];
unordered_map<ll,int>has;
vector<ll>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("%d",&a[i]);
    }
    ll sum=0;
    scanf("%d",&p);
    for(int i=1;i<=n;i++){
        sum+=a[i];sum-=p;
        hashy.push_back(sum);
    }
    hashy.push_back(0);
    sort(hashy.begin(),hashy.end());
    hashy.erase(unique(hashy.begin(),hashy.end()),hashy.end());
    int tt=0;

    add(lower_bound(hashy.begin(),hashy.end(),0)-hashy.begin()+1);
    ll ans=0;
    int x;sum=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];sum-=p;
        x=(lower_bound(hashy.begin(),hashy.end(),sum)-hashy.begin()+1);
        ans+=get(x);
        add(x);
    }
//    cout<<endl;
    cout<<ans<<endl;
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:41:9: warning: unused variable 'tt' [-Wunused-variable]
     int tt=0;
         ^
vudu.cpp:28:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
vudu.cpp:30:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
                          ^
vudu.cpp:33:19: 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 4 ms 504 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 461 ms 25280 KB Output is correct
5 Correct 246 ms 25764 KB Output is correct
6 Correct 380 ms 28844 KB Output is correct
7 Correct 432 ms 29412 KB Output is correct
8 Correct 330 ms 29412 KB Output is correct
9 Correct 445 ms 31072 KB Output is correct
10 Correct 383 ms 31072 KB Output is correct