oj.uz

Submission #37356

# Submission time Handle Problem Language Result Execution time Memory
37356 2017-12-24T14:49:35 Z IvanC Vudu (COCI15_vudu) C++14
140 / 140
 536 ms 30012 KB 
#include <bits/stdc++.h>
#define LSOne(S) (S & (-S))
using namespace std;
typedef long long ll;
const ll MAXN = 1000010;
ll bit[MAXN],vetor[MAXN];
void update(ll pos){
    while(pos < MAXN){
        bit[pos]++;
        pos += LSOne(pos);
    }
}
ll read(ll pos){
    ll ans = 0;
    while(pos > 0){
        ans += bit[pos];
        pos -= LSOne(pos);
    }
    return ans;
}
vector<ll> comp;
int main(){
    ll n;
    scanf("%lld",&n);
    comp.push_back(0);
    for(ll i=1;i<=n;i++) scanf("%lld",&vetor[i]);
    ll p;
    scanf("%lld",&p);
    ll soma = 0,resp = 0;
    for(ll i=1;i<=n;i++){
        soma += vetor[i];
        soma -= p;
        comp.push_back(soma);
    }
    sort(comp.begin(),comp.end());
    comp.erase(unique(comp.begin(),comp.end()),comp.end());
    soma = 0;
    for(ll i=0;i<=n;i++){
        soma += vetor[i];
        if(i)soma -= p;
        ll davez = lower_bound(comp.begin(),comp.end(),soma) - comp.begin() + 1;
        resp += read(davez);
        update(davez);
    }
    printf("%lld\n",resp);
    return 0;
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:24:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
                     ^
vudu.cpp:26:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(ll i=1;i<=n;i++) scanf("%lld",&vetor[i]);
                                                 ^
vudu.cpp:28:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&p);
                     ^

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17780 KB Output is correct
2 Correct 3 ms 17780 KB Output is correct
3 Correct 0 ms 17780 KB Output is correct
4 Correct 536 ms 30012 KB Output is correct
5 Correct 259 ms 30012 KB Output is correct
6 Correct 436 ms 30012 KB Output is correct
7 Correct 453 ms 30012 KB Output is correct
8 Correct 369 ms 30012 KB Output is correct
9 Correct 496 ms 30012 KB Output is correct
10 Correct 426 ms 30012 KB Output is correct